[백준] 18870 좌표 압축 (Python 파이썬)

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

18870번: 좌표 압축

문제 설명

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

---

풀이 과정

먼저, 좌표 압축이라는 것은 여러 곳에 흩뿌려진 좌표들을 연속된 수들로 모아 압축하는 것을 말한다.

예를 들어, 다음과 같은 좌표가 있다고 하자.

[1, 10, 10000, 1000000]

이렇게 네 점의 좌표가 있을 때, 좌표는 네 개 이지만 좌표값이 1부터 1,000,000 까지 있다.

하지만 이 좌표를 압축하여 순서대로 표현하면 [0, 1, 2, 3] 이 된다.

 

즉, 작은 값부터 시작해서 0부터 인덱스를 부여하는 방식이다.

1이 가장 작으므로 0이되고 10이 1, 10000이 2, 1000000이 3이 되는 것이다.

 

좌표압축을 위해 먼저 수들을 입력받은 후에,

정렬을 하기전에 앞서, 같은 수는 같은 좌표값을 가지므로 집합(Set)으로 중복값을 없애주자.

그리고 정렬을 해서 각 숫자들과 인덱스를 딕셔너리에 저장을 하면 된다.

 

이를 나타낸 파이썬 코드는 다음과 같다.

import sys
n = int(input())

numbers = list(map(int, sys.stdin.readline().rstrip().split()))

numset = set(numbers)
a = list(numset)
a.sort()

numdict = {}
for i in range(len(a)):
    numdict[a[i]] = i

for i in numbers:
    print(numdict[i], end=' ')

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !