[백준/파이썬] 18870 좌표 압축

📌문제

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

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

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

 

📌풀이

좌표 압축은 주어진 좌표를 상대적인 순서로 변환하는 과정
즉, 원래 좌표 값 자체가 아닌 해당 좌표가 크기 순으로 몇 번째인지 저장하는 방식

 

입력 받은 숫자들을 set으로 중복 제거 한 후 sorted로 정렬

 

원래 숫자가 몇 번째로 작은지 빠르게 찾기 위해 딕셔너리 사용

각 숫자가 몇 번째로 작은지(0-based index) 를 저장하는 역할

 

enumerate()는 리스트, 튜플 등 반복 가능한 객체(iterable)에 인덱스(index)를 붙여주는 함수

 

만약 nums= [2, 4, -10, 4, -9] 일 때

딕셔너리에 { -10: 0, -9: 1, 2: 2, 4: 3 } 이런 식으로 저장됨

 

기존 nums 배열을 압축된 값으로 변환하여 형식에 맞게 출력

 

📌코드

import sys

n = int(sys.stdin.readline().strip())
nums = list(map(int, sys.stdin.readline().split()))

sorted_unique = sorted(set(nums))  # 중복 제거 후 정렬

compression_map = {}  # 좌표 압축을 위한 딕셔너리 생성
for index, value in enumerate(sorted_unique):
    compression_map[value] = index
print(" ".join(str(compression_map[num]) for num in nums))