백준 18870 정렬&시간초과

문제 자체는 어렵지는 않았지만, 시간복잡도를 고려하지 않으면 시간초과가 나는 문제였다. 코테 문외한&초보인 나에게는 풀었는데 시간 초과가 나니 답답했던 문제 

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

18870번: 좌표 압축

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

풀이 

내 풀이(틀린 풀이)

import sys
N = int(input())
lst = []
lst = list(map(int, sys.stdin.readline().strip().split()))
sort_lst = sorted(set(lst))

new_lst = [sort_lst.index(i) for i in lst]
for i in new_lst:
    print(i, end=" ")

바뀐 풀이 

import sys
N = int(input())
lst = []
lst = list(map(int, sys.stdin.readline().strip().split()))
sort_lst = sorted(set(lst))
dic = {sort_lst[i]: i for i in range(len(sort_lst))}
for i in lst:
    print(dic.get(i), end=" ")

 

list.index[i]를 사용한 첫 풀이의 경우 시간복잡도 O(N)을 가지고 있기에(첫번째 배열부터 훑는 방식) 시간 초과가 나게 되어있다.

이를 해결하기 위해 dictionary를 이용해서 key-value로 값을 O(1)의 시간복잡도를 가지는 문제로 변형하였다.