[BOJ] 18870번: 좌표 압축 / Python - 값:인덱스 매핑을 사용한 성능 개선

https://www.acmicpc.net/problem/18870

최대 1,000,000개 숫자의 1차원 array가 주어졌을 때, 각 숫자에 대해 array 중 해당 숫자보다 작은 숫자들에 갯수를 출력하는 문제이다.

 

각 숫자가 unique하게 발생되는 목록을 sort한 것에서(unique_ordered), 숫자의 index를 찾으면 그 값이 곧 그 숫자보다 작은 숫자들의 갯수가 될 것이라고 생각해 풀이해봤으나 시간초과가 발생했다. 

시간 초과 발생 코드

import sys

x = tuple(map(int, sys.stdin.readlines()[1].rstrip().split()))
unique_ordered = sorted(set(x))
sys.stdout.write(" ".join(str(unique_ordered.index(i)) for i in x))

unique_ordered.index(i)는 list에서 특정 값의 index를 찾기 위해 list의 길이만큼 순차 검색을 수행한다. 이는 O(N) 시간이 걸리며, 이를 x의 모든 요소에 대해 반복하기 때문에 전체 복잡도가 O(N^2)가 된다. 1,000,000 ^ 2는 1조에 해당되므로 시간초과가 발생할 수밖에 없게 된다.

 

x의 각 숫자에 대해  unique_ordered를 매번 순회해서 index값을 찾는 대신에, unique_ordered를 단 1회 순회하면서 unique_ordered의 각 값과 index를 매핑하는 dict(아래의 index_map)를 만드는 방법이 있다.

정답 코드

import sys

x = tuple(map(int, sys.stdin.readlines()[1].rstrip().split()))
unique_ordered = sorted(set(x))
index_map = {v: i for i, v in enumerate(unique_ordered)}
sys.stdout.write(" ".join(str(index_map[i]) for i in x))

이렇게 코드를 수정하면, x의 모든 요소에 대해 index값 탐색이 dict 해싱 덕분에 O(1)로 해결된다. 즉 전체 x의 index 값 탐색은 O(N)에 해당된다.

 

정답 코드의 시간 복잡도

• set과 sorted (unique_ordered 만들기) → O(N log N)
• dict 생성 및 결과 조회 (index_map 만들기 및 전체 index값 조회 → O(N)

=> 전체 복잡도: O(N log N) 이 산출된다.