문제 이해하기
상자들의 목록이 주어졌다고 가정해 보겠습니다. 각 행은 해당 상자의 너비(width)와 높이(height)를 나타냅니다. 어떤 상자의 너비와 높이가 모두 다른 상자보다 작을 경우, 그 상자를 다른 상자 안에 넣을 수 있습니다. 우리의 목표는 하나의 상자 안에 최대 몇 개의 상자까지 중첩해서 넣을 수 있는지 구하는 것입니다.
예시
| 너비 | 높이 |
| 12 | 12 |
| 10 | 10 |
| 6 | 6 |
| 5 | 10 |
위 입력의 경우 출력은 3입니다. [6, 6] 상자를 [10, 10] 상자 안에 넣을 수 있고, 그 상자를 다시 [12, 12] 상자 안에 넣을 수 있기 때문입니다.
접근 방법
이 문제는 흔히 '러시아 인형 봉투(Russian Doll Envelopes)'라고 불리는 유형으로, LIS(최장 증가 부분 수열) 알고리즘과 이진 탐색(binary search)을 결합하면 O(n log n) 시간 복잡도로 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 모든 상자를 너비 기준 오름차순으로 정렬합니다. 너비가 같은 경우에는 높이 기준 내림차순으로 정렬하는데, 이렇게 하면 너비가 동일한 상자들이 서로 중첩되는 것으로 잘못 계산되는 것을 방지할 수 있습니다.
- 정렬된 순서대로 상자를 순회하면서, 각 상자의 높이가 들어갈 수 있는 위치를 이진 탐색으로 찾습니다.
- heights 배열은 지금까지 만들어진 중첩 수열의 높이 값을 관리하며, 새 상자의 높이가 들어갈 자리를 찾아 갱신합니다.
- 최종적으로 기록된 최대 중첩 깊이가 곧 정답이 됩니다.
구현 단계
insert_index()함수를 정의합니다. 배열 arr과 높이 this_h를 받아 이진 탐색으로 삽입 위치를 반환합니다.- l := 0, r := len(arr) - 1, res := 0 으로 초기화합니다.
- l <= r인 동안 반복합니다.
- m := l + (r - l) // 2 로 중간 인덱스를 계산합니다.
- cur_h := arr[m]
- cur_h < this_h이면 res := m, l := m + 1
- 그렇지 않으면 r := m - 1
- 반복이 끝나면 res + 1을 반환합니다.
- 메인 메서드에서는 다음을 수행합니다.
- 너비 기준(너비가 같으면 높이 내림차순)으로 행렬을 정렬합니다.
- n := 행렬의 항목 수
- heights := 크기가 n + 1인 리스트를 무한대(inf)로 채웁니다.
- heights[0] := 음의 무한대(-inf)
- res := 0
- 행렬의 각 상자에 대해
- [cur_w, cur_h] := box
- index := insert_index(heights, cur_h)
- heights[index] >= cur_h이면 heights[index] := cur_h
- res := max(res, index)
- res를 반환합니다.
다음 구현을 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, matrix):
matrix = sorted(matrix, key=lambda x: (x[0], -x[1]))
n = len(matrix)
heights = [float("inf")] * (n + 1)
heights[0] = float("-inf")
res = 0
for box in matrix:
cur_w, cur_h = box
index = self.insert_index(heights, cur_h)
if heights[index] >= cur_h:
heights[index] = cur_h
res = max(res, index)
return res
def insert_index(self, arr, this_h):
l = 0
r = len(arr) - 1
res = 0
while l <= r:
m = l + (r - l) // 2
cur_h = arr[m]
if cur_h < this_h:
res = m
l = m + 1
else:
r = m - 1
return res + 1
ob = Solution()
matrix = [
[12, 12],
[10, 10],
[6, 6],
[5, 10]
]
print(ob.solve(matrix))
입력
matrix = [ [12, 12], [10, 10], [6, 6], [5, 10] ]
출력
3
복잡도 분석
정렬에 O(n log n)이 소요되고, 각 상자마다 이진 탐색에 O(log n)이 걸리므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용되는 heights 배열의 공간 복잡도는 O(n)입니다. 완전 탐색으로 풀면 O(n²)이 걸릴 수 있는 문제를 훨씬 효율적으로 해결할 수 있는 것이 이 접근법의 가장 큰 장점입니다.