[LeetCode] 354 | Russian Doll Envelopes | Python

---

문제 링크: https://leetcode.com/problems/russian-doll-envelopes/

Russian Doll Envelopes - LeetCode

---

문제

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.

---

조건

• 1 <= envelopes.length <= $10^5$
• envelopes[i].length == 2
• 1 <= $w_i, h_i$ <= 105

---

내 풀이

envelop(w, h)이라 할 때, h가 작은 순서대로, h가 같을 때는 w가 큰 순서대로 정렬한다.

정렬된 envelop을 앞에서부터 보며, ans에는 w를 넣는다.

이미 h가 작은 순서대로 정렬되어있기 때문에, 앞에서부터 본다는 것은 h를 작은 순서대로 보는 것이다.

그렇기에 binary search로 적절한 w만 넣으면 된다.

---

코드

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes = sorted(envelopes, key=lambda x:(x[1], -x[0]))
        ans = [envelopes[0][0]]
        
        def binary(ans, n):
            left, right = 0, len(ans)-1
            
            while left <= right:
                mid = (left + right)//2
                
                if ans[mid] == n:
                    return mid
                elif ans[mid] > n:
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        
        for w, h in envelopes:
            if ans[-1] < w:
                ans.append(w)
            elif ans[-1] > w:
                idx = binary(ans, w)
                ans[idx] = w
                
        return len(ans)