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

문제 설명

풀이 전략

문제를 분석해보면 N개의 숫자가 주어지고 각 숫자에 대해 자기보다 작은 숫자의 수를 출력해야한다. N의 범위가 $1\leq N \leq 1,000,000$ 이고, 입력 숫자의 범위는 $-10^9 \leq X_i \leq 10^9$ 이다.
출력해야 하는 값은 자신보다 작은 값의 갯수이므로, 중복을 제거하고 정렬된 배열에서의 인덱스를 출력하면 된다. 여기서 그대로 출력 시 각 숫자에 대해 정렬된 배열속의 인덱스를 찾게 되면 매 번 배열을 순회하는 것과 마찬가지 이므로 시간이 초과된다. 이 때 정렬된 배열의 값과 인덱스를 딕셔너리 형태로 저장하면 출력 시에도 한번에 조회가 가능하므로 해결가능하다.

코드

import sys
n = int(sys.stdin.readline().rstrip())
arr = list(map(int,sys.stdin.readline().rstrip().split()))
arr2 = list(sorted(set(arr))) # 중복 제거
numdict={arr2[i]: i for i in range(len(arr2))}
for i in range(n):
    print(numdict[arr[i]],end=' ')

• 참고 - 한 줄에 출력할 때 출력 방법을 아래로 하면 시간이 더 줄어든다.

print(*[numdict[i] for i in arr])