<Hard> Russian Doll Envelopes (LeetCode : C#)

https://leetcode.com/problems/russian-doll-envelopes/

📕 문제 설명

봉투의 너비와 높이를 담은 envelop 배열이 주어진다. 마트료시카처럼 한 봉투를 다른 봉투 안에 넣는 과정에서 최대로 넣을 수 있는 봉투 개수 반환하기

봉투를 다른 봉투에 넣을려면 너비와 높이가 넣을 봉투보다 큰 봉투가 필요하다.

(봉투는 회전이 불가능하다.)

• Input
  봉투 정보
• Output
  최대로 넣을 수 있는 봉투 개수

예제

풀이

최장 증가 수열 (LIS)를 이용한 풀이이다. LIS 배열을 갱신해나가면서 최종적으로 오름차순으로 가장 긴 부분을 찾아서 길이를 반환해주면 된다.

• 최장 증가 수열: 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열

public class Solution
{
    public int MaxEnvelopes(int[][] envelopes)
    {
        // width 기준 정렬 -> height 기준 정렬 
        Array.Sort(envelopes, (v1, v2) => v1[0] == v2[0] ? v2[1] - v1[1] : v1[0] - v2[0]);
        int n = envelopes.Length;
        var minValue = new int[n];
        minValue[0] = envelopes[0][1]; // LIS 배열 (초기 값 setting = 제일 처음 값의 height)
        int pos = 0;
        for (int i = 1; i < n; i++)
        {
            int value = envelopes[i][1]; // 그 다음 봉투의 height
            if (minValue[pos] < value) // 현재 들어올 값이 더 큼
            {
                pos++;
                minValue[pos] = value; // minValue 배열 다음에 할당해주기
                continue;
            }
            // 만약 중간에 끼워 넣어야 하는 상황이면 
            int l = 0;
            int r = pos;
            while (l < r) // 이분탐색으로 위치 찾아주기
            {
                int mid = (l + r) / 2;
                if (minValue[mid] >= value)
                {
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }

            minValue[l] = value; // 이분탐색으로 찾아진 위치에 value 갱신
        }

        return pos + 1;
    }
}

결과