[백준] 좌표압축(18870번)-Python

✅문제

---

 

✅풀이 - (시간 초과)

---

import sys

sys.stdin.readline()
num_list = list(map(int,sys.stdin.readline().rstrip().split()))
rank = sorted(set(num_list))

for i in num_list:
    print(rank.index(i),end=" ")

 

해설

입력 받은 수를 set()를 통해 중복을 제거하고 정렬하여 for 문을 통해 index를 찾아 출력하였다.

 

❗❗❗시간  초과 발생 이유 ( .index() method ) 

마지막 출력문에서 num_list 를 탐색하며 index(method)를 사용하는데

.index() method는 리스트를 순회하며 값을 찾으므로 시간 복잡도가 O(N)이 된다.

👎.index() method를 num_list만큼 반복하므로 시간 복잡도가 O(N^2)이 되므로 시간 초과가 발생하였다.

 

 

✅풀이 - 통과

---

import sys

sys.stdin.readline()
num_list = list(map(int,sys.stdin.readline().rstrip().split()))

rank_dict = {num:index for index,num in enumerate(sorted(set(num_list)))}

print(" ".join(map(str,[rank_dict[i] for i in num_list])))

 

해설

위의 시간 초과가 발생하는 이유가 index() 메소드를 반복하기 때문이다.

이 문제를 해결하기 위해서 enumerate() method를 사용하여 index, num 을 key:value로 갖는 rank_dict를 만들어 주었다.

👍dictionary의 경우 시간 복잡도가 O(1) 이므로 N번 반복해도 시간 복잡도가 O(N)이 되어 시간 초과 문제를 해결 할 수 있다.!!