[알고리즘] 백준 18870번 좌표 압축

---

18870번 좌표 압축
이번 문제는 또 시간 초과가 떴다..
사실 시간 복잡도때문에 시간 초과가 뜰 걸 알고있었지만 막상 뜨니 해결법을 모르겠어서 찾아보았다.
혼자 고민하는 시간도 어느정도 가지면 좋겠지만.. 지금은 스펀지처럼 미친듯이 파이썬 사용 방법을 흡수하는 중이라 다른 사람의 방식들을 많이 참고하였다.

코드

import sys

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))

temp_nums = list(set(nums))
temp_nums.sort()
comp = {temp_nums[i]:i for i in range (len(temp_nums))}

for j in nums:
    print(comp[j], end=' ')

문제가 됐던 부분은 해당 index 숫자보다 작은 숫자의 개수를 세서 출력하는 부분이다.
이중 포문을 써버려서 시간 복잡도가 안드로메다로 가버렸지만.. 이 파이썬의 dictionary를 사용하여 index 값과 해당 배열의 값을 매치하여 저장해두면 기적적으로 시간 복잡도를 줄일 수 있던 것이었다..
딕셔너리를 사용하는 방법을 잘 터득해 온전히 나의 것으로 만들어야겠다.

+) 딕셔너리 = {“KEY” : “VALUE”} 이며 KEY는 중복이 허용되지 않는다. 만약 중복될 경우 마지막에 입력된 KEY의 VALUE를 출력한다고.