89. 18870 (좌표압축)

import sys
input = sys.stdin.readline

N = int(input())

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

result = {arr[i]: i for i in range(len(arr))}

for i in num:
    print(result[i], end=" ")

문제 요약

x좌표가 들어왔을 때 효율적으로 탐색할 수 있게 좌표압축을 구현해라

설명

좌표압축의 개념은 아래에 들어가보자.

https://smhope.tistory.com/235

좌표압축

먼저

arr = sorted(list(set(num)))

집합으로 변환하여 값의 중복을 제거해주고 리스트 형태로 바꾼다음 오름차순 정렬을 하였다.

 

다음은 데이터 사전을 이용하였다.

index를 사용해서 값을 뽑아낸다면 시간초과가 발생할 것이다.

result = {arr[i]: i for i in range(len(arr))}

만약 

5
2 4 -10 4 -9

값을 입력한다면

순서대로 진행하면서 result에는 값이

{-10: 0, -9: 1, 2: 2, 4: 3}

다음과 같이 저장될 것이다.

 

그것을

for i in num:
    print(result[i], end=" ")

통해 처음 입력 한 값을 key로 사용하여 value를 뽑아낸다면 답을 구할 수 있다.