BOJ 18870: 좌표 압축

Note

좌표 압축(Coordinate Compression) 기법을 직접 구현하는 문제입니다. 큰 범위의 좌표를 상대적인 크기 순서대로 작은 범위의 인덱스로 매핑하는 것이 핵심입니다.

---

문제

수직선 위에 N개의 좌표 X1, X2, …, XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, …, XN에 좌표 압축을 적용한 결과 X’1, X’2, …, X’N를 출력해보자.

문제 링크: https://www.acmicpc.net/problem/18870

입력

첫째 줄에 N이 주어진다.

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

출력

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

---

알고리즘 이론: 좌표 압축 (Coordinate Compression)

**좌표 압축(Coordinate Compression)**은 값의 크기 순서를 유지하면서 큰 범위의 좌표를 작은 범위의 인덱스(0, 1, 2, …)로 매핑하는 기법입니다.

핵심 아이디어

1. 중복 제거: 고유한 값들만 추출합니다.
2. 정렬: 추출된 고유값들을 크기 순으로 정렬합니다.
3. 인덱스 매핑: 정렬된 순서대로 0부터 시작하는 인덱스를 부여합니다. (딕셔너리/해시맵 활용)

필요성

좌표의 범위는 매우 크지만(예: -10⁹ ~ 10⁹), 실제로 사용되는 값의 개수(N)는 상대적으로 적을 때 유용합니다.

• 배열의 인덱스로 직접 사용하기 어려운 큰 값을 처리할 수 있습니다.
• 메모리를 효율적으로 사용하면서 정렬 순서를 유지할 수 있습니다.

시간 복잡도

• 중복 제거 및 정렬: $O(N\log N)$
• 딕셔너리 생성: $O(K)$ ($K$는 고유한 값의 개수)
• 압축 적용: $O(N)$
• 전체: $O(N\log N)$

---

해결 방법

1. set()을 사용하여 입력받은 좌표들의 중복을 제거합니다.
2. sorted()를 사용하여 오름차순 정렬합니다.
3. 정렬된 리스트를 순회하며 각 값에 대해 인덱스를 부여한 딕셔너리({값: 인덱스})를 생성합니다.
4. 원본 배열의 각 값을 딕셔너리에서 찾아 압축된 결과값을 출력합니다.

---

코드 구현

Python 구현

import sys
 
readline = sys.stdin.readline
 
n = int(readline())
arr = list(map(int, readline().rstrip().split()))
 
# 1. 중복 제거 및 정렬
sorted_unique = sorted(set(arr))
 
# 2. 딕셔너리 생성 (값 -> 인덱스)
# 각 값보다 작은 서로 다른 좌표의 개수는 곧 정렬된 배열에서의 인덱스와 같습니다.
compression_map = {value: i for i, value in enumerate(sorted_unique)}
 
# 3. 좌표 압축 적용 및 출력
result = [compression_map[x] for x in arr]
print(' '.join(map(str, result)))

---

예제 동작 과정

예제 입력: arr = [2, 4, -10, 4, -9]

1. 중복 제거 및 정렬:

   • set(arr) = {2, 4, -10, -9}
   • sorted_unique = [-10, -9, 2, 4]

2. 딕셔너리 매핑 생성:

   • -10 → 0 (자기보다 작은 값 0개)
   • -9 → 1 (자기보다 작은 값 1개: -10)
   • 2 → 2 (자기보다 작은 값 2개: -10, -9)
   • 4 → 3 (자기보다 작은 값 3개: -10, -9, 2)
   • compression_map = {-10: 0, -9: 1, 2: 2, 4: 3}

3. 압축 결과:

   • 2 → 2
   • 4 → 3
   • -10 → 0
   • 4 → 3
   • -9 → 1
   • 출력: 2 3 0 3 1

---

주의사항

1. 중복 처리: 문제에서 “Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수”라고 명시했으므로, 중복된 값은 한 번만 세어야 합니다.
2. 검색 효율성: 압축된 값을 찾을 때 list.index()를 사용하면 $O(N^2)$이 되어 시간 초과가 발생하므로, 반드시 $O(1)$인 **딕셔너리(해시맵)**를 사용해야 합니다.
3. 입력 최적화: $N$이 최대 $1,000,000$이므로 sys.stdin.readline 사용이 권장됩니다.

---

관련 알고리즘

• 정렬 (Sorting)
• 해시맵 (HashMap)