백준 18870번 좌표 압축

백준 18870번: 좌표 압축

아이디어

좌표중 가장 작은 숫자부터 순서대로 압축된 좌표를 할당한다. 가장 작은 값을 가지는 좌표는 0으로, 그 다음은 1… 이렇게 하려면 우선 입력받은 좌표를 정렬하고, 중복을 제거하고, 좌표를 압축해야 한다.

1. 좌표 정렬 - sort()를 사용하면 O(NlogN)의 시간복잡도로 좌표를 정렬할 수 있다.
2. 중복 제거 - 처음에는 리스트를 순회하며 in 연산자로 일일이 확인한 후에 append하여 중복을 제거했다. 이렇게 구현하면 시간복잡도가 O(N^2)가 돼서 시간초과가 난다. 파이썬에서 제공하는 자료구조인 set를 활용하면 O(N)의 시간복잡도로 중복을 제거할 수 있다.
3. 좌표 압축 - 리스트에 [0, 1]과 같은 방법으로 저장하여 탐색하면 시간초과가 난다. 따라서 해시테이블에 원래 좌표와 압축된 좌표를 저장해야 한다. O(1)의 시간복잡도로 탐색할 수 있게 된다. 파이썬에서 제공하는 자료구조인 dictionary를 활용해보자.

코드

import sys
input = sys.stdin.readline

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

sortedPoints = list(sorted(set(points)))
compressedPoints = {sortedPoints[i]: i for i in range(len(sortedPoints))}

for i in points:
    print(compressedPoints[i], end=' ')

여담

집합으로 만드는 것과 in을 사용해서 중복을 제거하는 것이 같은 시간복잡도를 가질 줄 알았는데 아니었다. 덕분에 한참 헤맸다..