항해99 리부트코스 알고리즘 2주 3일차 백준 18870 좌표 압축

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

 

 

• 주어진 좌표 리스트에서 각 좌표를 압축하여 새로운 좌표 리스트를 만듦
• 압축된 좌표는 각 좌표의 크기 순서에 따라 번호를 매기는 방식
• 예, 주어진 좌표가 [2, 4, -10, 4, -9]라면, 이 좌표를 크기 순으로 정렬하면 [-10, -9, 2, 4, 4]가 된다. 이때 압축된 좌표는 [2, 4, 0, 4, 1]입니다.

접근 방법

 

• 주어진 좌표 리스트에서 중복을 제거하고 정렬하여 순위를 매긴다
• 원래 좌표 리스트에서 각 좌표의 압축된 값을 찾는다.

 

즉, 이를 순서대로 구체적으로 표현하면 다음과 같다.

 

 

• 좌표 리스트를 입력받는다
• 중복을 제거한 후 정렬된 좌표 리스트를 만든다
• 정렬된 좌표 리스트를 이용해 각 좌표의 압축된 값을 딕셔너리에 저장
• 원래 좌표 리스트를 순회하면서 압축된 값을 출력

 

 

import sys
input = sys.stdin.read

# 입력
data = input().split()
n = int(data[0])
coords = list(map(int, data[1:]))

# 중복을 제거하고 정렬
sorted_unique_coords = sorted(set(coords))

# 압축된 좌표 사전 생성
coord_dict = {value: index for index, value in enumerate(sorted_unique_coords)}

# 결과 출력
compressed_coords = [coord_dict[x] for x in coords]
print(' '.join(map(str, compressed_coords)))

 

 

• 입력 데이터를 한 번에 읽어와서 필요한 부분을 분리
• 중복을 제거하고 정렬하여 고유한 좌표 리스트를 생성
• 고유한 좌표 리스트를 이용해 압축된 좌표 값을 사전에 저장
• 원래 좌표 리스트를 순회하면서 압축된 값을 출력