[BOJ] 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을 공백 한 칸으로 구분해서 출력한다.

📍 제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

📚 예제

Ex1)

5
2 4 -10 4 -9

2 3 0 3 1

Ex2)

6
1000 999 1000 999 1000 999

1 0 1 0 1 0

📌 풀이

리스트로 받고, 집합으로 겹치는 수 빼내고, 다시 리스트 사용해서 정렬한 다음 딕셔너리를 사용해서 푼다.
자료형을 다 사용할 줄 알면 풀 수 있는 문제다

사실 처음에 리스트랑 집합만 썼다가 시간 초과다 떴다. 딕셔너리 너무 좋아,,

🔨 시간 초과 난 코드

import sys
N = int(sys.stdin.readline())
ary = [int(x) for x in sys.stdin.readline().split()]
S = set(ary)
ans = list(S)
ans.sort()

for i in ary:
    for j in range(len(ans)):
        if(i == ans[j]):
            print(j, end=' ')

🔑 python 코드

import sys
N = int(sys.stdin.readline())
ary = [int(x) for x in sys.stdin.readline().split()]
dic = {}
ans = list(set(ary))
ans.sort()
for i in range(len(ans)):
    dic[ans[i]] = i

for i in ary:
    print(dic[i],end = ' ')