백준 18870 - 좌표압출(정렬)

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

18870번: 좌표 압축

 

 

시간 초과난 코드 1

n=int(input())

arr=list(map(int,input().split()))
arr2 = sorted(list(set(arr)))

for i in range(n):
    for j in range(len(arr2)):
        if arr[i]==arr2[j]:
            print(j,end=' ')
            break

우선 정렬 sorted를 사용해서 nlog이지만

위 출력하는 로직에서  최대 n번 X arr2의 길이 (n번)이므로 O(N^2)이다.

 

 

시간 초과난 코드 2

n=int(input())

arr=list(map(int,input().split()))
arr2 = sorted(list(set(arr)))

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

위 출력 로직 또한 arr을 순회하는동안 N번 arr2를 순회하면 Index를 찾는동안 n번 으로 O(N^2)이다.

 

 

 

정답 코드

n=int(input())

arr=list(map(int,input().split()))
arr2 = sorted(list(set(arr)))

dic=dict()
for i in range(len(arr2)):
    dic[arr2[i]]=i

for x in arr:
     print(dic[x], end = ' ')

딕셔너리를 사용해서 해쉬 자료구조로 O(1)으로 탐색을 해서 최종적으로 nlogn으로 해결 !