문제를 분석해보면 새로 생성된 좌표 X`은 Xi > Xj를 만족하는 좌표의 갯수를 의미하는 것을 알 수 있다. 이는 i번째 좌표보다 작은 좌표의 갯수가 압축된 좌표임을 나타내는데, 핵심은 어떻게 특정 좌표보다 작은 좌표의 갯수를 구하는것이다. 가장 단순하게 이중 for문을 사용하며 부르트포스 방식으로 탐색한다면 O(n^2) 으로 시간초과가 발생한다. 따라서 다른 방법을 떠올려야한다. 입력을 보았을때 가장 작은 숫자는 항상 0으로 압축이된다. 이를 바탕으로 좌표를 오름차순으로 정렬하고 i=1, i번째 좌표가 i-1번째 좌표보다 클 경우 이전 좌표값에서 1을 증가시켜주는 방법으로 갯수를 파악할 수 있다. 이 방법을 사용하면 O(n) 만에 특정 값보다 작은 값의 갯수를 구할 수 있다. #include #inc..
