[백준] 18870 - 좌표압축

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

18870번: 좌표 압축

문제 한줄 이해

-주어진 N개의 좌표들을 대소관계를 유지하면서 좌표 압축하기.

 

생각난 풀이

1번째 방법: 처음에는 단순히 값들의 대소관계를 유지하면서 각 좌표의 값들을 +1,-1 등을 하면서 좌표 사이의 갭을 줄여나가면 된다고 생각했다. 하지만 좌표값의 범위가 컸고 갭차이가 크면 시간복잡도가 커질것이라 생각했고 어떤 좌표를 기준으로 갭을 줄여나가야 하는지 기준을 잡기가 어려웠다. 

고민을 하다가 출력 예제를 보고 오름차순 기준으로 인덱스 번호가 부여 되는것을 캐치하고 코드를 짰다.

 

import sys

n = int(sys.stdin.readline())
nlist = list(map(int, sys.stdin.readline().split()))
sublist = sorted(nlist)

#배열을 정렬하고 dic에 각 값들의 인덱스 위치를 저장 하기 위해
dic ={}
cnt = 0
for i in range(n):
#   dic에 없다면 순서를 부여하고 +1 
    if sublist[i] not in dic:
        dic[sublist[i]] = cnt
        cnt +=1

#원래의 배열을 보고 dic의 값 출력
for i in nlist:
    print(dic[i],end=' ')