[Baekjoon] Sort - 11870 좌표 압축

문제

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

 

풀이

좌표 압축이란?

Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수

 

1. 서로 다른 좌표이기 때문에 중복된 숫자 제거

2. 오름차순 정렬 시 index == 좌표 압축 결과

3. index 정보를 활용하여 입력 숫자에 맞는 좌표 압축 결과 출력

 

예시

1) 2, 4, -10, 4, -9가 주어진 경우

중복 숫자 제거: 2, 4, -10, -9

오름차순 정렬: -10(0), -9(1), 2(2), 4(3)

 

2) 1000, 999, 1000, 999, 1000, 999가 주어진 경우

중복 숫자 제거: 1000, 999

오름차순 정렬: 999(0), 1000(1)

 

코드

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
deduplication_number = sorted(list(set(numbers)))
score = {deduplication_number[i] : i for i in range(len(deduplication_number))}

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