[BOJ] #18879번: 좌표 압축

 

 

문제

수직선 위에 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
• -109 ≤ Xi ≤ 109

 

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

 

풀이

pypy로 제출했다.

좌표 압축에 있어 하나하나 비교해보면서 압축하는 것은 시간복잡도를 기하급수적으로 늘리는 지름길이다.

주어진 수들을 먼저 정렬한 후, 그 순서를 출력하도록 하는 것이 효율적이다.

 

(1) 퀵정렬을 통해 리스트를 정렬했다.

(2) 중복되는 값은 set()을 통해서 제거했다.

(3) dictionary로 좌표 압축 값을 저장했고, 바로 불러올 수 있도록 했다.

* 리스트.index() 함수는 시간 복잡도 n^2를 가질 수 있으므로 자제해야겠다.

 

 

import sys
n = int(sys.stdin.readline())
n_list = list(map(int, sys.stdin.readline().split()))

def quicksort(array):
    if len(array) <= 1:
        return array
  
    pivot = array[-1]
    less, more, equal = [], [], []
    for each in range(len(array)):
        each = array.pop()
        if each < pivot:
            less.append(each)
        elif each > pivot:
            more.append(each)
        else:
            equal.append(each)
    return quicksort(less) + equal + quicksort(more)

quick_list = quicksort(list(set(n_list.copy())))
i = 0
dic = {}
for q in quick_list:
    dic[q] = i
    i += 1
for n in n_list:
    print(dic[n], end=' ')