[Python]Baekjoon18870: 좌표 압축

좌표 압축 

2 초

512 MB

23877

10357

7865

41.623%

문제

수직선 위에 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

풀이

정석적인 풀이법이 존재합니다.

인덱싱(번호 매기기)

현재 숫자 나열을 배열에 집어넣거나 enumerate 함수를 통해 번호를 매겨준다음(indexing)

2차원 리스트 정렬

원래 숫자의 크기 순대로만 정렬하는 2차원 정렬을 수행하고

빈 배열형 리스트 만들기

빈 배열을 만들어 원래 저장해 놓은 index에 새로 만들어준 순서들을 부여하는 방식입니다.

a = input()
# 인덱싱
num = list(enumerate(list(map(int,input().split()))))
# 빈배열 만들기
lst = [0 for i in range(len(num))]
# 2차원 정렬
num.sort(key=lambda x:x[1])

# 빈 배열에 집어넣기
idx = -1
now = 0.5
for i in range(len(num)):
    if now != num[i][1]:
        idx += 1
        now = num[i][1]
        lst[num[i][0]] = idx
    else:
        lst[num[i][0]] = idx
print(*lst)