[BOJ / Python] 18870 좌표 압축 (Class 3)

문제 링크

성능 요약

메모리: 291612 KB, 시간: 1284 ms

분류

값 / 좌표 압축(coordinate_compression), 정렬(sorting)

문제 설명

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

풀이 과정

그대로 탐색해버리면 백만 * 백만이라 무조건 시간 초과가 난다.

미리 정렬을 해준 뒤, 중복되는 값들은 필요 없으므로 set()을 통해 중복 제거를 해준다. 그리고 이를 내림차순으로 정렬해준다.

그리고 맨 처음 수부터 중복 제거된 크기에서 1씩 값을 빼주면서 값을 채워주면 되는데, 그 이유는 남은 값들의 개수가 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같기 때문이다.

예를 들어서

[5, 4, 5, 3, 2, 5, 1, 2] 이라는 배열이 있고, 이를 중복 제거해준다음에 내림차순으로 정렬해주면
[5, 4, 3, 2, 1]이 된다.
5일 때, Xi > Xj를 만족하는 서로 다른 좌표의 개수는 4개
4일 때는 3개,
3일 때는 2개
이런 식으로 내려가기 때문이다.

코드

import sys

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))

d = dict()

_X = [0] * N
for i in range(N) :
    _X[i] = X[i]
    
X = list(set(X))
X.sort(reverse = True)

n = len(X) - 1
for x in X :
    d[x] = n
    n -= 1
    
for x in _X :
    print(d[x], end=" ")