[백준 2751] 좌표 압축하기(실버2) - Python

문제

수직선 위에 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

시간 초과된 코드

문제 자체가 어렵진 않았는데 2번이나 시간 초과가 걸렸다.
처음에는 2중 for문을 사용해서 시간 초과가 걸리지 않을까 싶었는데 역시나..

import sys

n = int(sys.stdin.readline())

result = [0] * n
nums = list(map(int, sys.stdin.readline().rstrip().split()))

for i in range(n):
    cnt = 0
    for j in range(n):
        if nums[i] > nums[j]:
            cnt += 1
    result[i] = cnt

for r in result:
    print(r, end=' ')

그 다음에는 index()를 사용해서 코드를 다시 짜보았는데 또 시간 초과.
알고 보니 index()가 O(n)이라 얘도 O(n2)이라 위 코드나 마찬가지..

import sys

n = int(sys.stdin.readline())

result = [0] * n
nums = list(map(int, sys.stdin.readline().rstrip().split()))
nums_sorted = sorted(nums)

for i in range(n):
    x = nums_sorted.index(nums[i])
    result[i] = x

for r in result:
    print(r, end=' ')

성공한 코드

그래서 딕셔너리를 사용해서 새로 코드를 짰다.

import sys

n = int(sys.stdin.readline())

nums = list(map(int, sys.stdin.readline().rstrip().split()))
nums_set = sorted(list(set(nums)))

nums_dict = {}
for i in range(len(nums_set)):
    nums_dict[nums_set[i]] = i

for num in nums:
    print(nums_dict[num], end=" ")

우선 리스트에 좌표를 다 받고, set()를 사용해서 중복을 다 제거한 후에 sort()한다.
그리고 그 값들로 좌표를 key, index를 value로 하는 딕셔너리를 만들어 둔다.

여기서 index는 좌표 x보다 작은 숫자의 개수와 동일하기 때문에 nums들 돌면서 딕셔너리에서 해당 값을 찾아 순서대로 print해주면 된다.