백준 18870 <좌표 압축> Python

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

---

좌표 압축 문제입니다.

우선 제한시간이 2초이고 N <= 1,000,000 이기 때문에 정렬이 가능합니다. sort 함수의 시간 복잡도는 O(NlogN) 이기 때문입니다.

다만 중복되는 수가 있을 수 있으므로 중복 제거 처리를 해준 뒤 정렬해 앞에서부터 오름차순으로 번호를 붙여 출력만 해주면 됩니다.

---

import sys
from collections import defaultdict

input = sys.stdin.readline


def solution(N, nums):
    # 중복 수 제거
    comp_nums = list(set(nums))
    # 정렬
    comp_nums = sorted(comp_nums)
    # 순회하며 압축
    comp_dict = defaultdict(int)
    for i in range(len(comp_nums)):
        comp_dict[comp_nums[i]] = i
    
    print(*[comp_dict[num] for num in nums])

    
# 입력
N = int(input().strip())
nums = list(map(int, input().strip().split()))

solution(N, nums)