[백준][Python] 18870

백준 18870번 문제를 푸는데 시간 초과가 계속 발생해서 단순히 for문의 반복 횟수 때문인 줄로만 알았는데, 아니었다. 처음 나의 풀이는 아래 코드와 같았다.

N = int(input())
axis = [*map(int, input().split())]
axis_sort = sorted(set(axis))
result = {}
for point in axis:
    result[point] = axis_sort.index(point)
    print(result[point], end = " ")
print("")

처음에는 단순히 dictionary에 값을 넣고 한 번 더 조회하기 때문에 생기는 문제였나? 라는 생각을 했다. 하지만 dictionary의 경우 시간복잡도는 O(1)임을 놓쳤기 때문에 이런 생각을 하고 있었다. 문제는 list.index()에서 발생한 거였다. list.index()의 경우 O(N)의 시간복잡도를 가지고 있다. 이를 해결하려면 index로 조회하는 것이 아니라, key를 통해 value를 조회해야했다(dictionary). 아래는 이를 이용해 시간초과를 해결한 코드이다.

N = int(input())
axis = [*map(int, input().split())]
axis_sort = sorted(set(axis))
compressed_axis = {axis_sort[i]: i for i in range(len(axis_sort))}
for point in axis:
    print(compressed_axis[point], end=" ")
print("")

앞으로 값 조회를 할 때 시간 복잡도를 고려하여 코드를 짜도록 해야겠다.