[백준][파이썬]18870번: 좌표 압축

문제 출처 : www.acmicpc.net/problem/18870

18870번: 좌표 압축

내 풀이(시간초과)

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))

for i in arr:
    print(arr2.index(i), end = ' ')

내 풀이(성공)

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr2 = sorted(list(set(arr)))
dic = {arr2[i] : i for i in range(len(arr2))}
for i in arr:
    print(dic[i], end = ' ')

설명

풀이 자체는 어렵지 않았다.

set함수를 통해 중복을 없애준 후 정렬시킨 새로운 리스트를 만들어 준 후에 arr를 순서대로 돌면서 새로만든 arr2에서 해당 값의 인덱스를 뽑아주면 되는 문제였다.

하지만 시간초과가 떠서 조금 고민하게 만들었는데, 시간복잡도에 대한 고려를 해주지 않은게 그 원인이었다.

list.index(i)의 형태는 시간복잡도 O(N)을 가지고 있고 그렇다면 매번 최대 1,000,000번의 수행이 이루어지게 돼서

시간초과가 나는 것이었다.

때문에 이를 해결하기 위해 dict를 사용하기로 했다.

{ dict[요소] : 요소의 index }의 형태로 저장해 줌으로써 dict[i]의 형태로 시간복잡도 O[1]로 답을 뽑을 수 있게 하였고

문제를 통과했다.

 

결론

dict, sort, set에 대해 알고있다면 크게 어렵지 않게 해결할 수 있는 문제였다.

+

list.index(i) 형태의 시간 복잡도 = O(N)

index[i] 형태의 시간 복잡도 = O(1)