[백준] 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 ≤ N ≤ 1,000,000
-109 ≤ Xi ≤ 109

예제 입력

5
2 4 -10 4 -9

예제 출력

2 3 0 3 1

풀이

Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수를 구하기 위해 오름차순으로 정렬한 후, 누적합을 사용하여 배열의 원소를 key 로, 해당 원소까지의 누적합을 value로 하는 딕셔너리를 생성하여 해결했다.

처음에는 누적합을 따로 배열을 생성하여 저장한 후 딕셔너리에 추가해주었는데, 굳이 따로 배열을 생성해서 누적합을 구할 필요 없이, 바로 딕셔너리에서 누적합 계산이 가능하단걸 알았다.

첫번째 풀이, 누적합 배열 따로 계산 후 딕셔너리에 추가

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
sub_arr = sorted(arr) # key 용
sub_sum = [0]*(n+1) # value 용
dic = {}
for i in range(1, len(arr)): # value(누적합 계산)
   if sub_arr[i] == sub_arr[i-1]: sub_sum[i] = sub_sum[i-1]
   else: sub_sum[i] = sub_sum[i-1] + 1 
# 계산결과 딕셔너리에 저장
for i in range(len(sub_arr)):
   dic[sub_arr[i]] = sub_sum[i]
# 정답 출력
for key in arr:
   print(dic[key], end= " ")

두번째 풀이, 딕셔너리에서 바로 누적합 계산

import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
sub_arr = sorted(arr)
dict = {}
dict[sub_arr[0]] = 0

for i in range(1, len(sub_arr)):
    if sub_arr[i] == sub_arr[i-1]:
        dict[sub_arr[i]] = dict[sub_arr[i-1]]
    else:
        dict[sub_arr[i]] = dict[sub_arr[i-1]] + 1
for key in arr:
    print(dict[key], end=" ")