[BOJ / 파이썬] 18870: 좌표 압축

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

단계 : 정렬

알고리즘 분류 : 정렬, 값 / 좌표 압축

 

풀이:

처음 문제를 봤을 때 그냥 중복 제거하고 정렬해서 리스트 하나 만든 다음에 입력받은 값들을 넣어둔 리스트에 index를 출력하도록 하면 되겠다 하고 생각이 바로 들었다.

import sys

t = int(sys.stdin.readline())

ls = list(map(int, sys.stdin.readline().split()))
temp = list(sorted((set(ls))))

#시간 부족
for item in ls:
    print(temp.index(item), end=" ")

이런식으로 하면 되지 않을까 했는데 시간 부족이 나왔다. for 문 안에서 index 메서드를 쓰는 것이 효율적이지 못한 것 같아서 다른 방법을 생각하기로 했다.

 

시간 복잡도 면에서 더 간단한 방법이 무엇이 있을까 생각해보았고 딕셔너리 변수 하나를 만들어 숫자를 키로하여 순서를 저장하면 되지 않을까 했다.

 

temp에는 입력된 숫자들이 중복 없이 정렬되어 있으므로 temp를 이용하여 temp[i]를 키로 하고 i를 대응하는 값으로 가지는 딕셔너리를 만들어 저장하였고 이를 출력하는데에 사용하였다.

 

코드

import sys

t = int(sys.stdin.readline())

ls = list(map(int, sys.stdin.readline().split()))
temp = list(sorted((set(ls))))

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

for item in ls:
    print(dic[item], end=" ")