📚 출처 - 18870 - 좌표 압축
문제 설명
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
입출력 예
예제 입력 | 예제 출력 |
---|---|
5 2 4 -10 4 -9 | 2 3 0 3 1 |
6 1000 999 1000 999 1000 999 | 1 0 1 0 1 0 |
Logic
1.set
을 이용해 중복되는 값을 제거해준 후, set은 sort를 적용시킬 수 없으므로 list로 변경 후sort
를 통해 정렬
2. 앞서 전체를 순회하려면 O(N)의 시간 복잡도가 소요되지만,dict
을 이용하면 O(1)의 시간 복잡도로 이용할 수 있다. 그 점을 이용해dict
을 생성해주면 이 문제는 간단히 해결할 수 있다.
import sys
input = sys.stdin.readline
N = int(input())
coordinates = list(map(int, input().split()))
compare = sorted(list(set(coordinates)))
for i in range(len(coordinates)):
coordinates[i] = compare.index(coordinates[i])
for i in coordinates:
print(i, end = " ")
import sys
input = sys.stdin.readline
N = int(input())
coordinates = list(map(int, input().split()))
compare = sorted(list(set(coordinates)))
dic = {compare[i] : i for i in range(len(compare))}
for i in coordinates:
print(dic[i], end = " ")