[🥈2 / 백준 18870 / 파이썬] 좌표 압축

 

18870번: 좌표 압축

 

문제

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -10^9 ≤ Xi ≤ 10^9

예제 입력 1 5 2 4 -10 4 -9	예제 출력 1 2 3 0 3 1
예제 입력 2 6 1000 999 1000 999 1000 999	예제 출력 2 1 0 1 0 1 0

 

 

풀이

 

 

입력된 숫자들을 작은 순서대로 순위별로 바꿔 0순위부터 출력하는 문제이다.

 

 

처음 생각한 방법은 이렇다.

 

우선 입력된 숫자 리스트를 L이라고 할 때, L의 숫자를 중복없이 만든 뒤 정렬한 L2를 만든다.

 

그리고 L을 순서대로 순환하며 L2에서 인덱스를 찾아 출력한다.

 

아래는 위 알고리즘의 코드이다.

 

import sys
n = int(sys.stdin.readline())
L = list(map(int,sys.stdin.readline().split()))
rank = sorted(list(set(L)))
for i in L:
    print(rank.index(i),end=" ")

 

문제없이 잘 작동하였으나, 제출하니 시간 초과가 발생한다.

 

검색을 해 보니 딕셔너리형으로 정렬 후 출력하는 방법이 훨씬 빠른 것 같다.

 

아래는 정답 코드이다.

 

import sys
n = int(sys.stdin.readline())
L = list(map(int,sys.stdin.readline().split()))
rank = sorted(list(set(L)))
L2={rank[i]:i for i in range(len(rank))}
print(*[L2[i] for i in L])