[백준] 18870 파이썬(python) : 좌표 압축 - (★)

18870번: 좌표 압축

 

 

 

dict를 사용하면 시간복잡도 O(1)로 줄일 수 있습니다.

 

 

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

tmp = sorted(list(set(answer))) #1
dict = { tmp[i] : i for i in range(len(tmp))} #2
for i in answer:
    print(dict[i], end=" ") #3

 

 

#1 : 중복값을 없애주고 리스트화한 후에 정렬한 임시 리스트를 만든다.

#2 : 리스트 만들듯이 hash를 key : value = 값 : 인덱스 관계로 생성

#3 : answer에 받은 값 마다 key로 인식하여 value값을 출력하도록 하면 인덱스가 출력된다.

 

 

이 문제는 설명이 부실한데 예제에서 [ 2, 4, -10, 4, -9 ]를 입력 받아서 [ 2 3 0 3 1]을 출력하라고 합니다.

출력값은 다른게 아니라 오름차순으로 정렬했을때의 인덱스 값이다. (그래서 0이 있는것고 -10의 인덱스는 0) 좌표 압축이 뭔지 검색해도 새로운 알고리즘도 아니어서 이게 뭐지 생각했지만 다른 블로그의 해설 코드를 보고 인덱스 순서를 출력하라는 의미인지 이해했습니다.

 

 

그래서 중복값을 없애고 정렬한 후 정렬된 인덱스를 hash에 값 : 인덱스 관계로 입력하면 문제에서 원하는 대로 출력 가능

 

 

#2와 같이 hash를 입력받는 방법도 있다는걸 배울 수 있었습니다.