354. Russian Doll Envelopes

문제

You are given a 2D array of integers envelopes
where envelopes[i] = [wi, hi] represents the width and the height of an envelope.

One envelope can fit into another
if and only if both the width and height of one envelope are greater than the other envelope's width and height.

Return the maximum number of envelopes
you can Russian doll (i.e., put one inside the other).

Note: You cannot rotate an envelope.

2차원 정수 배열 envelopes가 주어집니다. 여기서 envelopes[i] = [wi, hi]는 봉투의 너비와 높이를 나타냅니다.

한 봉투가 다른 봉투 안에 들어갈 수 있으려면 다음 두 조건이 모두 만족되어야 합니다:

• 봉투의 너비와 높이가 모두 다른 봉투의 너비와 높이보다 커야 합니다.

봉투를 회전시킬 수 없으며, 한 봉투 안에 다른 봉투를 넣을 수 있는 최대 봉투 개수를 반환하세요.

---

예시

• 입력: [[5,4],[6,4],[6,7],[2,3]]
• 출력: 3

설명:

• [2, 3] 이 [5, 4] 안에 들어감
• 이게 [6, 7] 안에 들어감
• 총 3개

---

제한

• $1 <= envelopes.length <= 10^5$
• $envelopes[i].length == 2$
• $1 <= wi, hi <= 10^5$

---

풀이

1. 정렬
   너비를 기준으로 오름차순 정렬한 후, 너비가 같을 경우 높이에 대해 내림차순 정렬한다.

   • 예: [[5,4],[6,4],[6,7],[2,3]] → 정렬 후 [[2,3],[5,4],[6,7],[6,4]]

2. LIS 알고리즘 사용
   정렬된 높이에 대해 Longest Increasing Subsequence (LIS) 알고리즘을 적용한다.

   • bisect_left를 활용해 현재 높이가 들어갈 위치를 찾고, LIS 배열을 갱신한다.
   • 최종적으로 LIS 배열의 길이가 답이 된다.

---

코드

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key=lambda k: (k[0], -k[1]))  # 너비 오름차순, 높이 내림차순 정렬

        lis = []

        for width, height in envelopes:
            left = bisect_left(lis, height)  # 높이에 대해 LIS 위치 찾기

            if left >= len(lis):  # 현재 높이가 LIS 배열의 가장 끝에 추가될 경우
                lis.append(height)
            else:  # LIS 배열의 기존 값을 대체
                lis[left] = height

        return len(lis)  # LIS 배열의 길이가 최대 봉투 개수

시간 복잡도

• 정렬: $O(n \log n)$
• LIS 탐색 및 업데이트: $O(n \log n)$
• 총 시간 복잡도: $O(n \log n)$

공간 복잡도

• LIS 배열에 사용되는 공간: $O(n)$