Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 러시아 인형 봉투(Russian Doll Envelopes) 문제

문제 개요

높이와 너비가 한 쌍으로 주어진 여러 개의 봉투가 있다고 가정해 보겠습니다. 어떤 봉투를 다른 봉투 안에 넣으려면, 안에 들어갈 봉투의 높이와 너비가 모두 바깥쪽 봉투보다 작아야 합니다. 이 조건을 만족하면서 서로 중첩할 수 있는 봉투의 최대 개수는 얼마일까요?

예를 들어 입력이 [[5,5], [6,4], [6,8], [2,3]]이라면 정답은 3입니다. 가장 작은 봉투인 [2,3]부터 시작하여 [5,5], 그리고 [6,8] 순서로 차례대로 넣을 수 있기 때문입니다.

해결 접근 방식

이 문제는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘과 이진 탐색을 결합하면 O(n log n)의 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 배열 v를 높이(a[0]) 기준으로 오름차순 정렬합니다. 높이가 같을 경우에는 너비(a[1])를 내림차순으로 정렬하는데, 이렇게 하면 높이가 동일한 봉투끼리 서로 중첩되는 상황을 자연스럽게 방지할 수 있습니다.
  • v의 크기가 0이라면 즉시 0을 반환합니다.
  • 결과를 저장할 배열 ret을 선언합니다.
  • i를 0부터 v의 크기까지 반복하며 다음 과정을 수행합니다.
    • temp = v[i]로 설정하고, x = temp[1](현재 봉투의 너비)을 저장합니다.
    • low = 0, high = ret의 크기 - 1, curr = 0으로 초기화합니다.
    • low <= high인 동안 이진 탐색을 진행합니다. mid = low + (high - low) / 2로 계산하며, ret[mid] < temp[1]이면 curr = mid + 1, low = mid + 1로 갱신하고, 그렇지 않으면 high = mid - 1로 갱신합니다.
    • curr이 음수라면 해당 반복을 건너뛰고 다음 요소로 넘어갑니다.
    • curr이 ret의 크기보다 크거나 같다면 ret의 끝에 temp[1]을 삽입하고, 그렇지 않으면 ret[curr] = temp[1]로 기존 값을 교체합니다.
  • 모든 반복이 종료되면 ret의 크기를 반환합니다. 이 값이 곧 중첩 가능한 봉투의 최대 개수입니다.

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(vector <int> a, vector <int> b){
       if(a[0] == b[0])return a[1] > b[1];
       return a[0] < b[0];
    }
    int maxEnvelopes(vector<vector<int>>& v) {
       sort(v.begin(), v.end(), cmp);
       if(v.size() == 0)return 0;
       vector <int> ret;
       for(int i = 0; i < v.size(); i++){
           vector <int> temp = v[i];
           int x = temp[1];
           int low = 0;
           int high = ret.size() -1;
           int curr = 0;
           while(low <= high){
               int mid = low + (high - low) / 2;
               if(ret[mid]<temp[1]){
                  curr = mid + 1;
                  low = mid + 1;
               }else{
                  high = mid - 1;
               }
           }
           if(curr < 0) continue;
           if(curr >= (int)ret.size()){
              ret.push_back(temp[1]);;
           }else{
              ret[curr] = temp[1];
           }
       }
       return ret.size();
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{5,5}, {6,4}, {6,8}, {2,3}};
    cout << (ob.maxEnvelopes(v));
}

입력

{{5,5}, {6,4}, {6,8}, {2,3}}

출력

3