[딕셔너리] boj 18870. 좌표 압축

문제 해석

위 문제는 N개의 수가 주어질 때, 해당 수들이 일직선 상에서 왼쪽부터 "몇 번째" 숫자인지만 출력해주면 되는 문제다. 즉, 중복된 숫자의 개수는 고려하지 않아도 된다.(ㅎㅎ)

풀이 코드

첫 번째 생각

문제를 잘못 이해하고 짠 코드이다. 아래 코드는 예제 2를 3 0 3 0 3 0 으로 출력한다.

당연히 중복된 숫자가 나온 뒤에는 accumulative value를 계산해줘야 한다고 생각했는데, 그렇게 하면 예제 2에서 3 0 3 0 3 0이 나오는 게 맞다. 그래서 고민하다가, "아, 그냥 동일 숫자는 동일 순번만 뽑아주고 넘어가는구나..."라고 이해했다. 코드 순서를 고려해서 기껏 구현해놨더니 내 생각보다는 더 단순한 문제였다.

# N개의 수가 주어지고 : 1 <= N <= 1,000,000
# N개의 수 각 항을 자기보다 작은 수의 개수로 변환

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

t = int(input())
d = dd(int)
li = list(map(int,input().split()))
order = -1
acc = 0
_li = li.copy()
_li.sort(key=lambda x : x)
# for i in _li: print(i, end=' ')
for i in range(t):
    if i > 0 and _li[i] == _li[i-1]:
        d[_li[i]] = order
        # print(d[_li[i]])
        acc += 1
        # print(acc)
    else:
        order += 1
        order = order + acc
        acc = 0
        d[_li[i]] = order
for i in li:
    print(d[i], end=' ')

두 번째 생각 : 정답

# N개의 수가 주어지고 : 1 <= N <= 1,000,000
# N개의 수 각 항을 자기보다 작은 수의 개수로 변환

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

t = int(input())
d = dd(int)
li = list(map(int,input().split()))
order = -1
acc = 0
_li = li.copy()
_li.sort(key=lambda x : x)
for i in range(t):
    if i > 0 and _li[i] == _li[i-1]:
        d[_li[i]] = order
    else:
        order += 1
        d[_li[i]] = order
for i in li:
    print(d[i], end=' ')