문제 설명
서로 다른 값들로 이루어진 리스트가 있고, 각 숫자를 비내림차순(오름차순) 순서대로 하나씩 제거한다고 가정해 보겠습니다. 이때 각 숫자가 실제로 삭제되는 순서대로 해당 숫자의 인덱스를 찾아야 합니다.
예를 들어 입력이 nums = [4, 6, 2, 5, 3, 1]이라면 출력은 [5, 2, 3, 0, 1, 0]이 됩니다. 과정을 살펴보면 다음과 같습니다.
- 먼저 1을 삭제하면 배열은 [4, 6, 2, 5, 3]이 됩니다.
- 다음으로 2를 제거하면 [4, 6, 5, 3]
- 3을 제거하면 [4, 6, 5]
- 4를 제거하면 [6, 5]
- 5를 제거하면 [6]
- 마지막으로 6을 제거하면 빈 배열이 됩니다.
접근 방법
이 문제는 병합 정렬(Merge Sort)을 응용하면 O(n log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 병합 과정에서 왼쪽 절반보다 큰 값이 오른쪽에 몇 개 있는지를 추적하여, 각 숫자가 삭제될 때 앞서 제거된 원소의 개수를 계산하는 원리입니다.
해결 단계는 다음과 같습니다.
- my_sort() 함수를 정의합니다. 이 함수는 인덱스 리스트 inds를 매개변수로 받습니다.
- inds의 크기가 1 이하라면 inds를 그대로 반환합니다.
- sorted_inds := 새로운 리스트를 생성합니다.
- mid := inds의 크기를 2로 나눈 값
- left := my_sort(inds[0부터 mid까지]), right := my_sort(inds[mid부터 끝까지])
- i := 0, j := 0으로 초기화합니다.
- i가 left의 크기보다 작고 j가 right의 크기보다 작은 동안 반복합니다.
- nums[left[i]] < nums[right[j]]라면 sorted_inds의 끝에 left[i]를 추가하고 i를 1 증가시킵니다.
- 그렇지 않다면 sorted_inds의 끝에 right[j]를 추가하고, larger[right[j]]에 (left의 크기 - i)를 더한 후 j를 1 증가시킵니다.
- left[i부터 끝까지]를 sorted_inds에 추가합니다.
- right[j부터 끝까지]를 sorted_inds에 추가합니다.
- sorted_inds를 반환합니다.
메인 로직에서는 다음을 수행합니다.
- larger := nums와 같은 크기의 리스트를 만들고 0으로 초기화합니다.
- my_sort(0부터 nums의 크기까지의 범위)를 호출합니다.
- num_larger_pairs := (nums, larger)의 각 요소를 쌍(pair)으로 묶은 뒤 정렬합니다.
- num_larger_pairs의 모든 요소 e에 대해 e[1] 값으로 구성된 리스트를 반환합니다.
Python 코드 예제
더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다.
class Solution:
def solve(self, nums):
return solve(nums)
def solve(nums):
def my_sort(inds):
if len(inds) <= 1:
return inds
sorted_inds = []
mid = len(inds) // 2
left, right = my_sort(inds[:mid]), my_sort(inds[mid:])
i = j = 0
while i < len(left) and j < len(right):
if nums[left[i]] < nums[right[j]]:
sorted_inds.append(left[i])
i += 1
else:
sorted_inds.append(right[j])
larger[right[j]] += len(left) - i
j += 1
sorted_inds.extend(left[i:])
sorted_inds.extend(right[j:])
return sorted_inds
larger = [0] * len(nums)
my_sort(range(len(nums)))
num_larger_pairs = sorted(zip(nums, larger))
return [e[1] for e in num_larger_pairs]
ob = Solution()
nums = [4, 6, 2, 5, 3, 1]
print(ob.solve(nums))
입력
[4, 6, 2, 5, 3, 1]
출력
[5, 2, 3, 0, 1, 0]
복잡도 분석
이 알고리즘은 병합 정렬 기반이므로 시간 복잡도는 O(n log n)이며, larger 배열과 재귀 호출에 필요한 공간 때문에 공간 복잡도는 O(n)입니다. 단순히 매번 최솟값을 찾아 제거하는 방식(O(n²))보다 훨씬 효율적입니다.