C++ 알고리즘 풀이: 직사각형을 서로 삽입한 뒤 남는 최소 개수 구하기

문제 이해하기

N개의 서로 다른 직사각형에 대한 너비와 높이 정보가 주어졌을 때, 직사각형을 서로 안에 삽입(중첩)하는 과정을 거친 후 마지막에 남게 되는 직사각형의 최소 개수를 구하는 것이 목표입니다.

두 직사각형 R1과 R2의 너비를 각각 W1, W2, 높이를 H1, H2라고 할 때, W1 < W2이고 H1 < H2를 만족하면 R1은 R2 안에 완전히 들어갈 수 있습니다. 따라서 가장 작은 직사각형은 두 번째로 작은 직사각형 안에, 그 직사각형은 다시 더 큰 직사각형 안에 차례대로 중첩시킬 수 있습니다.

예를 들어 입력이 {{30, 45}, {15, 15}, {45, 30}, {60, 75}}라고 해보겠습니다. 두 번째 직사각형(15×15)을 첫 번째 직사각형(30×45) 안에 넣고, 다시 그 직사각형을 네 번째 직사각형(60×75) 안에 넣으면 겉으로 보이는 것은 세 번째 직사각형(45×30)과 네 번째 직사각형뿐입니다. 따라서 정답은 2가 됩니다.

해결 전략

이 문제는 널리 알려진 '러시아 인형 봉투(Russian Doll Envelopes)' 문제와 구조가 유사합니다. 핵심 아이디어는 다음과 같습니다.

직사각형을 너비 기준 오름차순으로 정렬하되, 너비가 같은 경우에는 높이 기준 내림차순으로 정렬합니다. 너비가 같은 직사각형은 서로 포함될 수 없으므로, 높이를 내림차순으로 정렬하면 잘못된 중첩을 자연스럽게 방지할 수 있습니다.
큰 직사각형부터 작은 직사각형 순서로 살펴보면서, 현재 직사각형이 들어갈 수 있는 중첩 사슬(nested chain)을 이진 탐색으로 찾아 넣습니다. 들어갈 곳이 없다면 새로운 사슬을 만듭니다.
최종적으로 만들어진 사슬의 개수가 곧 남는 직사각형의 최소 개수입니다.

알고리즘 단계별 설명

n := boxes 배열의 크기로 설정합니다.
boxes 배열을 앞서 설명한 규칙(너비 오름차순, 같으면 높이 내림차순)에 따라 정렬합니다.
pair를 원소로 가지는 배열 nested를 선언합니다.
nested의 끝에 boxes[n - 1]을 삽입합니다.
i := n - 2부터 시작하여 i ≥ 0이 유지되는 동안 i를 1씩 줄여 가며 다음을 반복합니다.
- left := 0, right := nested의 크기 - 1로 초기화합니다.
- left ≤ right인 동안 다음을 반복합니다.
  - mid := (right + left) / 2로 설정합니다.
  - nested[mid]의 높이가 boxes[i]의 높이와 같거나, nested[mid]의 너비가 boxes[i]의 너비보다 작거나 같으면 left := mid + 1로 갱신합니다.
  - 그렇지 않으면 right := mid - 1로 갱신합니다.
- 반복 종료 후 left가 nested의 크기와 같다면, 현재 직사각형이 어떤 사슬에도 들어갈 수 없다는 의미이므로 nested의 끝에 boxes[i]를 새로 추가합니다.
- 그렇지 않다면 nested[left]의 너비와 높이를 boxes[i]의 값으로 교체합니다. 이는 해당 사슬의 맨 위 직사각형을 더 작은 직사각형으로 바꿔, 이후 더 많은 직사각형이 이 사슬에 들어올 수 있도록 하기 위함입니다.
모든 직사각형을 처리한 뒤 nested의 크기를 반환합니다. 이것이 곧 남는 직사각형의 최소 개수입니다.

C++ 구현 예제

다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

bool comp(const pair<int, int>& L, const pair<int, int>& R) {
    if (L.first == R.first)
        return L.second > R.second;
    return L.first < R.first;
}

int Rectangles(vector<pair<int, int>> &boxes) {
    int n = boxes.size();
    sort(boxes.begin(), boxes.end(), comp);
    vector<pair<int, int>> nested;
    nested.push_back(boxes[n - 1]);
    for (int i = n - 2; i >= 0; --i) {
        int right = nested.size() - 1, left = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second)
                left = mid + 1;
            else
                right = mid - 1;
        }
        if (left == nested.size())
            nested.push_back(boxes[i]);
        else {
            nested[left].second = boxes[i].second;
            nested[left].first = boxes[i].first;
        }
    }
    return nested.size();
}

int main() {
    vector<pair<int, int>> boxes = {{30, 45}, {15, 15}, {45, 30}, {60, 75}};
    cout << Rectangles(boxes);
}

실행 결과

입력

{{30, 45}, {15, 15}, {45, 30}, {60, 75}}

출력

시간 복잡도 분석

정렬에 O(n log n)의 시간이 소요되며, 각 직사각형마다 이진 탐색을 수행하므로 O(log n)의 추가 시간이 필요합니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 중첩 사슬을 저장하는 배열 때문에 최악의 경우 O(n)이 됩니다.