백준 18870번 <좌표 압축>

백준 알고리즘 18870번

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

18870번: 좌표 압축

---

18870번

수직선 위에 N개의 좌표가 있을 때, Xi를 좌표 압축한 결과는 Xi > Xj를 만족하는 서로 다른 좌표의 개수이다.

 

입력으로 첫 줄에 좌표의 개수 N이 주어진다. 둘째 줄에 공백 한 칸으로 주어진 각 좌표가 주어진다.

 

출력으로 각 좌표에 대해 좌표 압축한 결과를 공백 한 칸으로 구분하여 출력한다.

---

문제 해결

좌표의 list를 정렬해서 문제를 해결할 수 있다.

입력으로 주어진 좌표들에 대해 반복되는 좌표를 없애고 좌표의 list를 정렬한다.

이때 각 좌표의 정렬된 index가 좌표 압축한 결과이다. 따라서 해당 좌표를 key로 하고 좌표의 index를 value로 하여 dictionary를 만들고 원래의 좌표 list를 for문을 돌아서 해당 값을 key로 하는 value값을 출력하면 된다.

---

코드

import sys
input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
setN = list(set(num))
setN = sorted(setN)

number = {}
idx = 0
for n in setN:
    number[n] = idx
    idx += 1
for i in range(N):
    print(number.get(num[i]), end=" ")

---

결과

---