[Algorithm] Python : index 함수의 시간초과 해결법, Dictionary 이용 !

백준의 좌표압축(18870)번 문제를 풀다가 시간초과로 한참 고민함 .. ㅠㅠ

문제는 생각보다 쉬웠다.

 

해결방법은

 1. 입력받을 숫자개수(n)을 입력받고,

 2. n개 만큼의 숫자를 list로 받은 후, 

 3. set으로 중복을 제거하고,

 4. sort함수로 정렬한 후,

 5. 기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력하면 된다고 생각했다.

 

 근데, 여기서 시간초과가 발생한 것은 "기존 list로 입력받은 숫자 배열과 sort 함수로 정렬된 배열을 비교하여 index를 출력" 하는 부분이었다.

 

 원하는 값의 index를 출력하는 index()함수의 시간 복잡도는 배열의 원소 하나하나를 따져야하기 때문에 O(n)의 시간복잡도를 갖는다.

따라서, 배열의 원소들을 각각 비교하는데 index()함수를 사용한다면 시간 복잡도는 매우 클것이므로 시간초과 문제가 발생한다.. ㅠ

 

 

💡해결방법은 바로 dictionary를 사용하는 것 💡

일단 해결 코드는 다음과 같다.

n = int(input())

coor = list(map(int, input().split()))

to_set = set(coor)
to_list = list(to_set)
sorted = sorted(to_list)

result = []

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

for i in coor:
  print(dic[i], end=" ")

 

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

이 코드는 dictionary인 "dic"을 생성하는 코드로

실제 원소 값을 key ( = sorted[i] )

해당 원소의 index를 value ( = i for i in range(len(sorted)) ) 

로 두어

 

key를 통해 value 즉, index를 O(1) 시간 만에 찾을 수 있게 되었다.

 

 

 

 

파이썬 함수를 사용할 때는 시간초과 문제가 발생할 수 있으니 앞으로 잘 확인하자 ㅠㅠ !