문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
예제
나의 풀이1
import sys
input = sys.stdin.readline
N = int(input())
x_list = list(map(int, input().split()))
set_list = sorted(set(x_list))
for i in x_list:
print(set_list.index(i), end=" ")- 입력값 그대로의 리스트 `x_list`와 입력값에서 중복값을 제거하고 오름차순으로 정렬한 리스트 `set_list`를 따로 생성한다.
- for문을 실행해서 `set_list`에서 `x_list` 각 요소의 인덱스 값을 찾아서 출력한다.
- 하지만 이 풀이는 시간초과로 실패했다.
- 최대 `1,000,000`을 길이로 가질 수 있는 리스트에 for문으로 `index()`를 실행하는 게 시간 실행 시간을 증가시켰다.
다른 사람의 풀이
import sys
input = sys.stdin.readline
N = int(input())
x_list = list(map(int, input().split()))
set_list = sorted(set(x_list))
dic = {set_list[i] : i for i in range(len(set_list))}
for i in x_list:
print(dic[i], end=" ")- `{-10: 0, -9: 1, 2: 2, 4: 3}`와 같이 `set_list`의 요소를 키로, 인덱스를 값으로 가지는 딕셔너리를 생성한다.
- for문에서 딕셔너리의 인덱스로 접근하는 방식으로 값을 출력해서 시간 초과 문제를 해결했다.
- `list.index(i)` 형태의 시간 복잡도 = O(N)
- `index[i]` 형태의 시간 복잡도 = O(1)