백준 18870. 좌표 압축

 

 

생각보다는 까다로웠던 문제. 단순히 이중 반복문을 사용하면 금방 풀 수 있을 거라고 생각했지만, 보기 좋게 시간 초과가 떴다 ,,,

input 대신 성능이 좋은 sys.stdin.readline()을 이용해봐도 마찬가지.

 

그래서 이중 for문을 사용하지 않고 정렬 후 index 함수를 이용하는 방법을 선택했으나, 이 또한 실패했다.

분석해보니 index함수에서 어차피 다시 반복을 하니까 이중 반복문의 성능이 크게 개선되지 않은 듯 했다.

그래서 집합으로 바꾸고, 해당 인덱스를 딕셔너리에 넣는 방법으로 정리한 후, 리스트를 반복하며 출력하는 방법을 선택했다. 이렇게 하면 최악의 경우 n*n의 반복문이 돌 일이 없기 때문에 가능한 것으로 보인다.

 

import sys

n = int(sys.stdin.readline())
lst = list(map(int, sys.stdin.readline().split()))
lst_cp = list(set(lst))

lst_cp.sort()
dic = {lst_cp[i] : i for i in range(len(lst_cp))}
for i in lst:
	print(dic[i], end=" ")
print()