[백준] 18870번 좌표 압축

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

문제

풀이

문제가 이해 안돼서 문제 설명을 찾아봤다

간단히 말하면 좌표를 크기순으로 print 하는거다
가장 작은 수가 0번이고, 제일 큰수가 n이다

예를 들어 좌표가 -3 20 3 -1 -3 이라고 한다면, 답은 0 3 2 1 0이다.

팁은

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

첫번째 풀이 - 시간초과

import sys
input = sys.stdin.readline
n = int(input())
array = list(map(int, input().split()))
array2 = sorted(list(set(array)))

for i in range(len(array)):
    for j in range(len(array2)):
        if array[i] == array2[j]:
            array[i] = array2.index(array2[j])

for i in array:
    print(i, end=' ')

두번째 풀이

sorted(array)를 한 후에 dictionary에 { 숫자 : 인덱스 }를 넣고 각 숫자에 해당되는 인덱스를 print해줬다.

import sys
input = sys.stdin.readline
n = int(input())
array = list(map(int, input().split()))

array2 = sorted(list(set(array)))
dic = {array2[i] : i for i in range(len(array2))}

for i in array:
    print(dic[i], end = ' ')