[99클럽 코테 스터디] 22일차 TIL - 좌표 압축

문제 설명

18870번: 좌표 압축

 

 

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

입출력 예 설명
입력 1

5
2 4 -10 4 -9

출력 1 

2 3 0 3 1

 

‍💻내가 짠 코드

import sys

def coordinate_compression(n, arr):
    sorted_unique = sorted(set(arr))  # 중복 제거 후 정렬
    rank = {value: i for i, value in enumerate(sorted_unique)}  # 각 값의 압축된 좌표 매핑
    return [rank[x] for x in arr]  # 원래 배열 순서대로 변환된 값 반환

# 입력 받기
n = int(sys.stdin.readline().strip())
arr = list(map(int, sys.stdin.readline().split()))

# 결과 출력
print(*coordinate_compression(n, arr))

✍ 접근 방법

 

• 중복 제거 후 정렬
  sorted(set(arr))을 통해 중복된 값을 제거하고 정렬하여 고유한 좌표를 작은 값부터 정렬된 상태로 만들기
• 압축 좌표 매핑
  enumerate(sorted_unique)를 사용하여 각 값이 몇 번째로 작은지(= 압축된 값) 딕셔너리에 저장
• 결과 변환
  원래 리스트의 값을 딕셔너리를 참고해 변환하여 새로운 리스트를 반환
• 입출력 최적화
  sys.stdin.readline()을 사용하여 빠르게 입력을 처리