[백준 18870][파이썬] 좌표 압축 (파이썬 dictionary)

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

18870번: 좌표 압축

처음 생각한 알고리즘은 다음과 같다.

 

1. 리스트를 새로운 집합으로 만들어서 중복을 제거한다.

 

2. 집합을 리스트로 바꾸어서 정렬 후 다시 리스트로 생성한다.

 

3. 새로운 리스트 요소들의 인덱스가 곧 자신보다 작은 요소들의 개수가 된다.

 

오름차순으로 정렬을 하게 되면 자연스럽게 인덱스가 자신보다 같거나 작은 요소의 개수가 된다.

 

자신보다 작은 요소를 구해야 하므로 중간에 집합으로 만드는 과정을 통해 중복을 제거한다.

 

이 방식으로 짠 코드는 다음과 같다.

 

import sys
n=int(sys.stdin.readline())
li=list(map(int, sys.stdin.readline().split()))
temp=list(sorted(set(li)))
for i in range(n):
    li[i] = temp.index(li[i])
for i in range(n):
    print(li[i], end=' ')

 

그러나 이러한 방식은 인덱스를 조사하는 과정에서 너무 많은 시간이 소모되고 결국 시간 초과가 발생했다.

 

인덱스를 조사하는 과정의 시간을 단축해야했다.

 

파이썬의 자료형인 dictionary를 사용하면 쉽게 해결할 수 있었다.

 

위의 1, 2번까지는 똑같은 과정을 진행하는데 3번을 변경해야한다.

 

list의 index 함수를 사용하는 것이 아니라 애초에 중복을 제거하고 정렬된 리스트에서 딕셔너리 자료형에 key-value 쌍으로 요소-인덱스를 넣어주면 된다.

 

그리고 출력할 때는 원래 인덱스의 값을 딕셔너리 자료형의 key값으로 넣어주면 된다.

 

import sys
n=int(sys.stdin.readline())
li=list(map(int, sys.stdin.readline().split()))
temp=list(sorted(set(li)))
dic = dict()
for i in range(len(temp)):
    dic[temp[i]]=i
for i in li:
    print(dic[i], end=' ')