[BOJ] 좌표 압축

---

코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

s = sorted(arr)    # 오름차순 정렬
d = dict()         # (key = 숫자, value = 작은값개수) 딕셔너리

for i in range(N):
    if i == 0:
        d[str(s[i])] = 0
        continue
    if s[i-1] == s[i]:    # 왼쪽숫자와 오른쪽숫자가 같은 경우
        d[str(s[i])] = d[str(s[i-1])]    # 작은값 개수가 같다
    else:    # 오른쪽숫자는 왼쪽숫자보다 크므로 작은값 개수가 왼쪽숫자의 작은값개수보다 1개 많다
        d[str(s[i])] = d[str(s[i-1])] + 1

# 처음 주어진 좌표의 각 숫자에 대해 작은값 개수를 딕셔너리에서 찾는다
ans = list(map(lambda x: d[str(x)], arr))
print(" ".join(map(str, ans)))

결과

풀이 방법

• 좌표를 먼저 오름차순 정렬한 다음, 순차적으로 0부터 순번을 매긴다
• 좌표가 정렬되어 있으므로 순번을 매길 때에는, 오른쪽 숫자가 왼쪽 숫자와 같으면 순번이 같고, 같지 않으면 순번이 1만큼 크다
• 정답을 출력할 때에는 원래 좌표의 순서에 맞게 순번을 출력해야 하므로 순번을 빠르게 찾기 위해 딕셔너리를 활용하였다.

---