[백준] 18870. 좌표 압축/Python - Silver2

❓문제

https://www.acmicpc.net/problem/18870

성능 요약

메모리: 149248 KB, 시간: 1824 ms

분류

값 / 좌표 압축, 정렬

 

문제 설명

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

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

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

✍🏻풀이

문제를 읽어보면 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수가 Xi'과 같다고 한다. 정말 단순하게 생각하면 이중반복문으로 풀 수 있다. 그러나 이 경우 시간 복잡도가 최악의 경우 O(N²)으로 N이 최대 1,000,000인 이 문제에서는 당연히 시간초과가 발생한다.

좌표 2, 4, -10, 4 ,-9 로 총 다섯개 가 주어졌다. 주어진 좌표를 보면 X는 중복된 값이 있을 수도 있다. 그러므로 우리는 set으로 중복된 값을 제거하고 다시 list로 바꿔 정렬한다.

그럼 정렬된 list는 -10, -9, 2, 4가 될 것이다. -10보다 작은 좌표의 수를 구하면 0이고, -9는 1, 2는 2, 4는 3임을 알 수 있다. 즉, 각 인덱스가 Xi > X를 만족하는 서로 다른 좌표의 개수가 됨을 알 수 있다. 이 때, for문을 써서 작성할 수도 있지만 더 간단하게 사전형태로 만들 수 있다.

for i in range(len(S)):        ➡️         dict(zip(S, range(len(S)))
	res[s[i]] = i

그리고 이를 이용하여 기존에 주어진 좌표 순서대로 값을 출력하면 된다.

💻코드

import sys

input = sys.stdin.readline

N = int(input())
X = list(map(int, input().split()))
S = sorted(list(set(X)))

res = dict(zip(S, range(len(S))))

for x in X:
    print(res[x], end=' ')

📍후기

N이 1,000,000인 것을 보고 어떻게 시간 복잡도를 줄여야 하나 계속 고민했다. 개수를 기록할 생각은 했지만 dict는 생각하지 못했다. 앞으로는 list로만 기록하기 어려울 것 같은 경우에는 dict도 고려해야겠다.