[python] 18870. 좌표 압축

• 문제 

---

 

 

 

• 잘못된 풀이

import sys
N = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
sorted_list = sorted(set(num_list))

answer_list = []
for i in num_list:
    idx = sorted_list.index(i) # O(n)의 시간 복잡도 -> 시간초과
    answer_list.append(idx)
print(*answer_list)

 

해당 문제는 입력한 숫자보다 작은 수가 몇 개나 있는지 체크하는 문제이다.

바로 떠오른 방법이 .index()로, 원하는 요소가 리스트 중에 몇 번째인지 그 인덱스를 return해주는 라이브러리이다.

하지만 .index()는 O(n)의 시간복잡도로, for문 안에서 썼을 때의 복잡도는 O(n^2)가 되기 때문에, 시간초과로 문제해결에 실패하였다.

 

 

 

• 올바른 풀이

import sys
N = int(input())
num_list = list(map(int, sys.stdin.readline().split()))
sorted_list = sorted(set(num_list))

answer_dict = {}
for i in range(len(sorted_list)):
    answer_dict[sorted_list[i]] = i

for i in num_list:
    print(answer_dict[i], end=' ')

 

.index()의 시간 복잡도를 줄이기 위한 방법으로, dictionary를 통해 인덱스를 구하는 방법을 적용하였습니다.

시간복잡도는 첫번째 for문 O(n), 두번째 for문 O(n)해서 전체 코드로는 O(n)입니다.

 

이전의 방법보다 더 적은 시간 복잡도로 코드를 구현할 수 있었습니다.