[백준]좌표 압축(18870) 파이썬

 

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

18870번: 좌표 압축

 

해당 문제를 풀이하는데 가장 먼저 든 생각은 중복제거, 정렬, 인덱스 구하기 였다.

 

두가지의 기능은 모두 파이썬의 내장함수 set(), sorted(), index()의 내장함수로 구현이 되어있다.

 

그래서 처음에 구현한 방법은 아래와 같았다.

 

number = int(input())
question = list(map(int, input().split()))

question2 = sorted(set(question))

for i in range(len(question)):
    print(question2.index(question[i]), end=' ')

그러나 안타깝게도 시간초과가 났다.

 

sorted()의 경우 최대 O(n^2) index()의 경우 최대 O(n)의 시간이 걸린다.

 

이 때 index()가 index를 찾기 위해 n * n이 걸릴 수 있다는 것을 간과하고 있었다.

input 함수 또한 바꾸어 진행하였다.

import sys

input = sys.stdin.readline

number = int(input())
question = list(map(int, input().split()))

question2 = sorted(set(question))
new_q = {question2[i]:i for i in range(len(question2))}

for i in question:
    print(new_q[i], end=' ')

 

함수의 시간복잡도를 생각하지 않고 구현하고 있어 생긴 문제였다.