[Python] 백준/BOJ 18870번: 좌표 압축 (Silver 2)

💻 Problem

문제 보러 가기

 

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해 보자.

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

 

💡 Approach

이 문제는 처음에 이해하기 힘들었다..

좌표 압축이 무슨 말인지,,, 왜 하는 건지,,

친구한테 설명을 듣고 나서야 이해했다.

 

x[i]를 압축한 값은 x[i]`이다
x[i]` 값은 X[i] > x[j]를 만족하는 x[j]의 개수이다
=> x[i]` 값은 x[i]보다 작은 수의 개수이다

 

왜 구하나 싶을 수도 있는데 상위 티어 문제로 가면 좌표압축을 활용한 문제들이 있나 보다.

좌표 압축을 하면 상대적인 거리를 저장하여 메모리 사용을 줄인다.

 

✏️ Solution

import sys
input = sys.stdin.readline

n = int(input())
x = list(map(int, input().split()))

sorted_x = sorted(set(x))

dic = {}
for i in range(len(sorted_x)):
    dic[sorted_x[i]] = i

for i in x:
    print(dic.get(i), end=' ')

• 시간복잡도: O(n)