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을 공백 한 칸으로 구분해서 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- -10⁹ ≤ Xi ≤ 10⁹
예제
예제 입력 1:
5
2 4 -10 4 -9
예제 출력 1:
2 3 0 3 1
예제 입력 2:
6
1000 999 1000 999 1000 999
예제 출력 2:
1 0 1 0 1 0
문제 분석
이 문제는 좌표 압축을 직접 구현하는 문제입니다.
핵심 포인트
- 좌표 압축 정의:
Xi보다 작은 서로 다른 좌표의 개수 - 중복 제거: 같은 값은 하나로 취급
- 정렬: 크기 순서대로 인덱스 부여
해결 방법
좌표 압축 알고리즘을 사용합니다:
- 중복 제거 및 정렬
- 딕셔너리로 값-인덱스 매핑 생성
- 원본 배열의 각 값을 압축된 값으로 변환
코드 구현
제공된 코드
import sys
readline = sys.stdin.readline
n = int(readline())
arr = list(map(int, readline().rstrip().split()))
sorted_arr = sorted(set(arr))
dict_arr: dict[int, int] = {}
for (i, e) in enumerate(sorted_arr):
dict_arr[e] = i
compress_arr = []
for e in arr:
print(dict_arr[e], end=' ')코드 분석
1. 입력 처리
import sys
readline = sys.stdin.readline
n = int(readline())
arr = list(map(int, readline().rstrip().split()))- 입력 최적화를 위해
sys.stdin.readline()사용 - N개의 좌표를 리스트에 저장
2. 중복 제거 및 정렬
sorted_arr = sorted(set(arr))set(arr): 중복 제거sorted(): 오름차순 정렬
3. 딕셔너리 생성
dict_arr: dict[int, int] = {}
for (i, e) in enumerate(sorted_arr):
dict_arr[e] = i- 각 값에 대해 정렬된 순서대로 인덱스 부여
- 예:
[-10, -9, 2, 4]→{-10: 0, -9: 1, 2: 2, 4: 3}
4. 좌표 압축 적용
for e in arr:
print(dict_arr[e], end=' ')- 원본 배열의 각 값을 딕셔너리에서 찾아 인덱스로 변환
- 바로 출력 (리스트에 저장하지 않음)
개선된 코드
더 Pythonic하게 작성한다면:
import sys
readline = sys.stdin.readline
n = int(readline())
arr = list(map(int, readline().rstrip().split()))
# 중복 제거 및 정렬
sorted_unique = sorted(set(arr))
# 딕셔너리 생성 (값 -> 인덱스)
compression_map = {value: i for i, value in enumerate(sorted_unique)}
# 좌표 압축 적용 및 출력
result = [compression_map[x] for x in arr]
print(' '.join(map(str, result)))개선 사항:
- 딕셔너리 컴프리헨션 사용
- 리스트 컴프리헨션으로 결과 생성
join()을 사용하여 출력 형식 개선
시간 및 공간 복잡도
시간 복잡도
- 중복 제거 및 정렬: O(n log n) - n은 원소 개수
- 딕셔너리 생성: O(k) - k는 고유한 값의 개수
- 압축 적용: O(n)
- 전체: O(n log n)
공간 복잡도
- 정렬된 배열: O(k) - k는 고유한 값의 개수
- 딕셔너리: O(k)
- 전체: O(k)
예제 동작 과정
예제 입력 1: n=5, arr=[2, 4, -10, 4, -9]
1. 중복 제거 및 정렬:
set(arr) = {-10, -9, 2, 4}
sorted(set(arr)) = [-10, -9, 2, 4]
2. 딕셔너리 생성:
dict_arr = {
-10: 0,
-9: 1,
2: 2,
4: 3
}
3. 좌표 압축 적용:
arr[0] = 2 → dict_arr[2] = 2
arr[1] = 4 → dict_arr[4] = 3
arr[2] = -10 → dict_arr[-10] = 0
arr[3] = 4 → dict_arr[4] = 3
arr[4] = -9 → dict_arr[-9] = 1
결과: 2 3 0 3 1
예제 입력 2: n=6, arr=[1000, 999, 1000, 999, 1000, 999]
1. 중복 제거 및 정렬:
sorted(set(arr)) = [999, 1000]
2. 딕셔너리 생성:
dict_arr = {999: 0, 1000: 1}
3. 좌표 압축 적용:
1000 → 1
999 → 0
1000 → 1
999 → 0
1000 → 1
999 → 0
결과: 1 0 1 0 1 0
주의사항
1. 중복 처리
set()을 사용하여 자동으로 중복을 제거합니다. 같은 값은 하나로 취급됩니다.
2. 정렬 순서
오름차순으로 정렬해야 올바른 인덱스가 부여됩니다:
- 작은 값 → 작은 인덱스
- 큰 값 → 큰 인덱스
3. 딕셔너리 사용
딕셔너리를 사용하면 O(1) 시간에 압축된 값을 찾을 수 있습니다:
# 효율적 (O(1))
compressed = dict_arr[value]
# 비효율적 (O(n))
compressed = sorted_arr.index(value) # 사용하지 말 것4. 입력 최적화
N이 최대 1,000,000이므로 input() 대신 sys.stdin.readline()을 사용해야 합니다.
관련 알고리즘
- 좌표 압축 (Coordinate Compression)
- Python 입력 최적화
- 정렬 (Sorting)