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

리스트의 매 원소마다 해당 원소보다 작은 고유한 원소들이 몇 개인지 세서 계산하는 방식을 쓰면 시간 초과가 나는 문제였다. 

 

prefix sum 방식과 유사하게, 해당 원소보다 작은 개수인 고유한 원소의 개수가 몇 개인지를 미리 unique_list 배열에 저장해 두고, 정답 배열에 이 값을 추가하는 방식으로 시간초과를 막을 수 있었다. 

import sys
from collections import defaultdict
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

unique_list = defaultdict(lambda: 0)
for index, a in enumerate(sorted(list(set(arr)))):
    unique_list[a] = index

ans = []
for a in arr:
    ans.append(str(unique_list[a]))
    
print(" ".join(ans))