[baekjoon] 18870번 : 좌표압축 by python

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

18870번: 좌표 압축

 

code

#좌표압축
import sys
input = sys.stdin.readline

n = int(input())

a = [int(x) for x in input().split()]
set_a = set(a)
list_a = list(set_a)
list_a.sort()
dic = {list_a[i]: i for i in range(len(list_a))}


for i in a:
    print(dic[i],end=" ")

 

 

처음 내가 작성한 코드는 아래와 같이 리스트만 사용하여 해결하였다.

import sys
input = sys.stdin.readline

n = int(input())

a = [int(x) for x in input().split()]
set_a = set(a)
list_a = list(set_a)
list_a.sort()

x = []
for i in range(len(list_a)):
    x.append([i,list_a[i]])


for i in a:
    for num,xi in x:
        if i == xi:
            print(num,end=" ")

이렇게 해결하니 문제점이 시간초과가 뜬다는 점이다.

리스트의 시간복잡도는 O(n)

딕셔너리의 시간복잡도 O(1)

시간초과를 해결하기위해선 딕셔너리로 바꿔 해결해야했다.

 

또한 처음 무작정 작성한 코드보다 딕셔너리를 사용함으로써 더 깔끔한 코드를 완성시킬수 있었다.

알고리즘문제를 풀때 시간복잡도를 조금 더 신경쓰면서 문제를 풀어나가야겠다.