백준 알고리즘 18870번 ‘좌표 압축’ 문제

문제 소개

입력 📝

첫째 줄에 N개의 좌표 개수가 주어지고
둘째 줄에는 N개의 좌표 X1, X2, …, XN이 공백으로 구분되어 주어져요

출력 📤

각 좌표 Xi를 압축한 결과 X’i를 출력해야 해요
X’i는 원래 좌표 Xi보다 작은 좌표들의 개수와 같아요

제한 조건:
1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9

첫 번째 시도 😥

Idea 🤔

처음엔 numpy 라이브러리가 생각났다
배열(array)을 사용해서 각 좌표마다 전체 리스트와 크기를 비교하면 간단하게 해결될 것이라 생각했다

Code

import sys
import numpy as np
from collections import Counter

n = int(sys.stdin.readline())
x_list = np.array(list(map(int, sys.stdin.readline().split())))

x_prime_list = list()

for x in x_list:
    x_prime = (x_list < x).sum()
    x_prime_list.append(x_prime)

print(*x_prime_list)

Result

실패! 😱

문제의 ‘서로 다른’ 좌표라는 조건을 놓쳐
같은 값을 가진 좌표도 모두 세어버리는 실수를 했다

두 번째 시도 😫

Idea 💡

‘서로 다른’ 좌표만 세어야 하니, Counter를 사용해 중복을 제거한 키(key)들로만 비교하면 되겠다고 생각했다

Code

import sys
import numpy as np
from collections import Counter

n = int(sys.stdin.readline())
x_list = list(map(int, sys.stdin.readline().split()))
x_counter = np.array(list(Counter(x_list).keys()))

x_prime_list = list()

for x in x_list:
    x_prime = (x_counter < x).sum()
    x_prime_list.append(x_prime)

print(*x_prime_list)

Result

런타임 에러 (Module Not Found) 😭

아뿔싸, 백준 온라인 저지 환경에서는 numpy를 지원하지 않는다는 사실을 간과했다

세 번째 시도 🤯

Idea 💡

numpy 없이 풀기 위해, 중복을 제거한 리스트를 정렬하면 어떨까 생각했다
정렬된 리스트에서 특정 값의 인덱스(index)는 곧 그 값보다 작은 값들의 개수와 같으니까
list.index() 메서드를 사용하면 되겠다고 판단했다

Code

import sys
from collections import Counter

n = int(sys.stdin.readline())
x_list = list(map(int, sys.stdin.readline().split()))
x_uniques = sorted(list(Counter(x_list).keys()))
x_prime_list = list()

for x in x_list:
    x_prime = x_uniques.index(x)
    x_prime_list.append(x_prime)

print(*x_prime_list)

Result

시간 초과 ⏰

for 루프 안에서 index() 메서드를 반복적으로 호출하는 것이 문제였다
index()는 내부적으로 리스트를 순회하기 때문에 시간 복잡도가 O(N)이고
결과적으로 전체 알고리즘의 시간 복잡도가 O(N^2)이 되어 시간 초과가 발생한 것 같았다

네 번째 시도 🎉

Idea ✨

시간 복잡도를 줄이기 위해
매번 index()로 찾지 말고, 미리 각 값의 인덱스를 저장해두면 어떨까?
딕셔너리(Dictionary) 를 사용해서 유니크한 값들을 key로, 정렬 후의 인덱스를 value로 저장해두고 필요할 때마다 바로 꺼내 쓰는 방식으로 개선하려 했다
이러면 탐색 시간이 O(1)에 가까워져 전체 시간 복잡도를 O(N log N) (정렬) + O(N) (탐색) 수준으로 줄일 수 있을 거라 생각했다

Code

import sys
from collections import Counter

n = int(sys.stdin.readline())
x_list = list(map(int, sys.stdin.readline().split()))
# set으로 중복을 제거하고 정렬
x_uniques = sorted(list(set(x_list))) 

x_dict = dict()
# 값과 인덱스를 딕셔너리에 저장
for i, x in enumerate(x_uniques):
    x_dict[x] = i

x_prime_list = list()
# 딕셔너리에서 바로 값을 찾아 추가
for x in x_list:
    x_prime_list.append(x_dict[x])

print(*x_prime_list)

Result

성공! ✅

드디어 통과!
딕셔너리를 활용해 탐색 시간을 획기적으로 줄인 것이 정답이었다

개선할 부분 🤔

Counter와 set을 활용하는 부분에서 더 간결한 코드로 개선할 여지가 있어 보인다!