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

백준 온라인저지 18870번 좌표압축

문제풀러 바로가기👇👇👇👇👇👇

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

18870번: 좌표 압축

 

 

 

문제풀이

---

시간 복잡도가 굉장히 중요한 문제이다.

근본적인 알고리즘은 쉬운 편이다. 중복되지 않은 배열을 정렬해 그 인덱스를 가져오면 된다.

만약 여기서 리스트에서 인덱스를 가져오는 index()메소드를 사용하면 시간복잡도가 O(N)이다. 그런데 문제에서 N의 범위는 무려 1 ≤ N ≤ 1,000,000 이기 때문에 하나의 인덱스를 구할 때 최악의 경우엔 1,000,000회의 동작을 수행해야한다. 당연히 시간초과가 발생할 것이다.

 

반면 딕셔너리를 사용하면 어떻게 될까?

딕셔너리를 사용하면  O(1)이다. 키를 입력하면 index()메소드처럼 따로 찾을 필요없이 바로 value를 돌려받을 수 있다.

따라서 이 문제에선 딕셔너리를 사용해야한다.

 

 

코드

 

- 시간초과된 풀이

n = int(input())
pos = list(map(int, input().split()))
zipped = sorted(list(set(pos)))


for i in pos:
    print(zipped.index(i), end=" ")

 

- 성공한 풀이

n = int(input())
pos = list(map(int, input().split()))
zipped = sorted(list(set(pos)))

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

for i in pos:
    print(dic[i], end=" ")