[백준 18870번-파이썬]좌표압축

백준 (BOJ) 18870번
https://www.acmicpc.net/problem/18870

사용언어 : PYTHON

1.문제

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

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

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

즉 [2,10,15,1,1] 라는 데이터가 있으면 값의 대소관계만 고려한 데이터로 변환하라는 것이다.
(위 예시의 정답 : [1,2,3,0,0])

2.풀이

각 원소의 중복을 제거하고 정렬 한 다음, 각 값에 0부터 순서를 부여하면 된다.
처음에는 index함수를 사용하여 위치를 출력하였는데, 이렇게하면 모든 원소에 대해서(N) index를 수행(O(N))하여 최종적으로 O(N**2)의 시간복잡도가 걸리게 되어 시간초과가 나왔다.
이를 해결하기 위해 dictionary에서 자신의 위치를 할당하여 바로 출력(=O(1)의 시간복잡도)하게 하였다.

3-1.시간초과 코드

import sys
input = sys.stdin.readline

_=int(input())
l=list(map(int,input().split()))

l_component=list(set(l))
l_component.sort()

for i in l:
    print(l_component.index(i),end=' ')  # O(n**2)의 시간복잡도

3-2.정답코드

import sys
input = sys.stdin.readline

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

l_component=sorted(list(set(l)))

l_dict={l_component[i]:i for i in range(len(l_component))}

for i in l:
    print(l_dict[i]) # O(N)의 시간복잡도