BOJ - 18870 좌표 압축 해결 전략 (C++)

• 문제

  수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

• 입력

1. 첫째 줄에 N이 주어진다.
2. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

• 출력

  첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

• 제한
  1 ≤ N ≤ 1,000,000
  -10^9 ≤ Xi ≤ 10^9

• 예제 입력 1
  5
  2 4 -10 4 -9
• 예제 출력 1
  2 3 0 3 1

해결 전략

  기초 정렬 PS 문제들 중 가장 깊이있는 사고를 요하는 문제가 아니었나 싶다. 모든이가 최초에 문제를 접할 때 가장 간단한 알고리즘이 떠오를 것이다. 배열을 마련한 후, N개의 정수를 입력받고, 중첩 반복문으로 x[i]보다 작은 요소의 개수를 count하는 방식 말이다. 하지만, N이 최대 1,000,000개이기 때문에 당연하게도 본 알고리즘으로는 시간 내에 문제를 해결할 수 없다.

  그 다음 시도해볼 수 있는 접근은, Topological Sorting 문제에서 많이 사용하는, '값을 기준으로 하는 배열'의 마련이다. 하지만, 이 역시 얼마 안가 폐기될 것임을 곧바로 알아차릴 수 있다. 값의 범위가 10^9으로, 매우 넓기 때문에 배열이든 벡터든 마련하기가 힘들기 때문이다.

  위의 두 시도가 불가능함을 알아차린 후, 본인은 학부 알고리즘 수업에서 배웠던 다음과 같은 아이디어가 떠올랐다.

배열에 정수를 저장하되, 값과 인덱스를 따로 분리해서 보존하자.

  이어서, 본 문제의 메모리 제한이 512MB임을 본 후, 이 방식이 아마 정답으로 이어질 것임을 예상할 수 있었다.

  "인덱스를 보존한다."

  인덱스 보존 본능은, 이처럼 문제의 입력 범위가 매우 넓어 기본적인 정렬 알고리즘을 반복문에 삽입하여 사용할 수 없을 때 충분히 고려해볼만한 아이디어다. 문제에 주어진 예시를 통해 이를 간단히 설명하겠다.

아래에 배열 x가 있다.

value : 2 4 -10 4 -9
x_index : 0 1 2 3 4
인 상태이다. 이때, 본 문제에서는, Xi보다 작은 Xj의 개수를 세어 Xi'으로 기억한다고 한다. 입력 범위가 넓어 Naive한 접근(중첩 반복문을 이용)이 어려움을 안 상태에서, 우리가 떠올릴 수 있는 방법은 무엇이 있을까.

  바로, 배열을 우선 Nondecreasing Order로 정렬하는 것이다.
value : -10 -9 2 4 4

  이때, 최초 입력 상태의 배열의 index값을 x_index라는 필드명으로 보존하면, 다음과 같다.
x_index : 2 4 0 1 3
(1과 3은 순서 상관x)

  이 '정렬된 상태'의 배열에서, 다시 인덱스를 새로 잡아보면,
value : -10 -9 2 4 4
new_index : 0 1 2 3 4
이다. 이제, 답이 보이기 시작할 것이다.

그렇다. 배열을 정렬해놓으면, 정렬 상태에서의 0 ~ n-1 인덱스가 곧 본 문제에서 찾고자 하는 Xi'값을 그대로 가리키게 된다.

  하지만, 이때, 위에서처럼, 문제가 하나 있다. 바로, 같은 값일 때이다. 이는 간단한 반복문 중첩을 통해 해결할 수 있으리라. 물론, 여기서의 중첩 반복문은 이론적으로는 O(n^2)이겠지만, 그러한 입력은 사실상 고려할 필요가 없으므로 크게 상관이 없다.

  이제 남은 것은, 정렬된 배열을 다시 한 번 정렬하는 것이다. 이때, 정렬의 기준은 value가 아니라 원래 key order로 돌아가기 위한 x_index이리라.

value : 2 4 -10 4 -9
x_index : 0 1 2 3 4
new_index : 2 3 0 3 1

이렇게 해서 문제를 해결할 수 있다. 실제 풀이에서는 new_index라는 필드명 대신, prime_index라는 필드명을 사용했다.

  참고로, 구현 측면에서 하나의 Key에 대한 다양한 정보를 유지보존하기 위해 구조체가 필요하다. 또한, algorithm 헤더의 sort 함수를 사용할 때, 정렬의 기준을 달리하여 두 번 정렬해주는 작업이 중요하다. 이는 아래 코드에서 그 기술을 확인할 수 있다. return type이 bool인 비교 함수를 만들면 된다. 기준 필드를 달리해서.

  아래는 코드이다.

#include <iostream>
#include <algorithm>
// BOJ - 18870 Coordinates Compression
using namespace std;

typedef struct {
	int value;
	int x_index;
	int prime_index;
}Coord;

Coord x[1000000];

bool pred_value(Coord a, Coord b) {
	if (a.value < b.value) return true;
	return false;
}

bool pred_x_index(Coord a, Coord b) {
	if (a.x_index < b.x_index) return true;
	return false;
}

int main(void) {
	int n, cnt = 0;
	Coord newItem;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> newItem.value; newItem.x_index = i;
		x[i] = newItem;
	}

	sort(x, x + n, pred_value);

	for (int i = 0; i < n; ) {
		x[i].prime_index = cnt;
		int j = i + 1;
		for ( ; x[j].value == x[i].value; j++)
			x[j].prime_index = cnt;
		i = j;
		cnt++;
	}

	sort(x, x + n, pred_x_index);

	for (int i = 0; i < n; i++) 
		cout << x[i].prime_index << ' ';

	return 0;
}