[Python] 백준 18870 : 좌표 압축 / 시간초과 극복

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

18870번: 좌표 압축

 

>> 막혔던 점 : 시간초과가 뜸

 

원래 코드

- set으로 각 숫자를 오름차순으로 나열했을 때 인덱스 값으로 대체할 생각

=>but, 시간초과 뜸

 

=> 문제원인

: 순차탐색으로 특정 값을 검색하려면 최대 O(n)의 시간이 걸림

: 따라서 키: 값 형식의 사전으로 시간 복잡도를 낮출 필요가 있음

 

==> 고친 코드

 

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

=> 각 숫자 : 키

=> 각 숫자의 오름차순 인덱스 : 값

 

ex)

list_num_temp = [-10, -9, 2, 4]

dic = {-10 :0, -9 : 1, 2 :2, 4 :3}

 

=>하나씩 찾아갔던 idnex를 키값을 통해 바로 찾음

=> 시간복잡도가 O(n) (n은 숫자 개수)에서 O(1)로 낮아짐