354. Russian Doll Envelopes ★★★

354. Russian Doll Envelopes

 

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # DP로 풀어야 함
        # 안에 들어가려면, 가로, 세로 둘다 다른것보다 작아야 함
        # 우선 정렬하고
        # envelope 리스트에는 계속 포함되는 거는 계속 추가하고
        # max_width, max_height 최대로 업데이트..
        # LIS 풀듯이 풀어보자!
        envelopes = sorted(envelopes, key=lambda k:(k[0], k[1]))
        
        # 자신 포함이니 1로 초기화
        dp = [1] * len(envelopes) # count 저장

        max_count = 0
        for i in range(len(envelopes)-1, -1, -1): # i는 뒤에서 부터
            for j in range(i+1, len(envelopes)):
                # i: len(envelopes)-1 부터 0까지
                # i< j-> len(envelopes)-1 까지
                if(envelopes[i][0] < envelopes[j][0] and envelopes[i][1] < envelopes[j][1]):                    
                    dp[i] = max(dp[i], dp[j]+1)
            max_count = max(max_count, dp[i])

        return max_count

 

로직은 맞지만, Time Limit Exceeded 으로 인해

-> 메모이제이션으로 변경

 

from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # 정렬: 가로와 세로 모두 오름차순으로 정렬
        envelopes = sorted(envelopes, key=lambda k: (k[0], k[1]))
        
        # 메모이제이션 딕셔너리
        dp = {}

        max_count = 1  # 최대 중첩 개수

        for i in range(len(envelopes) - 1, -1, -1):  # 역방향으로 탐색
            if i not in dp:  # 아직 계산되지 않은 경우만 처리
                dp[i] = 1  # 최소 자기 자신 포함
                for j in range(i + 1, len(envelopes)):
                    if envelopes[i][0] < envelopes[j][0] and envelopes[i][1] < envelopes[j][1]:
                        dp[i] = max(dp[i], dp[j] + 1)

            max_count = max(max_count, dp[i])  # 최대값 갱신

        return max_count

 

또는

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # DP로 풀어야 함
        # 안에 들어가려면, 가로, 세로 둘다 다른것보다 작아야 함
        # 우선 정렬하고
        # envelope 리스트에는 계속 포함되는 거는 계속 추가하고
        # max_width, max_height 최대로 업데이트..
        # LIS 풀듯이 풀어보자!
        envelopes = sorted(envelopes, key=lambda k:(k[0], k[1]))
        
        memo = {} # 메모이제이션을 위한 딕셔너리

        # 재귀 함수로 
        def call_dp(i):
            if i in memo:
                return memo[i]

            max_lengh = 1 # 최소 자기자신 포함
            for j in range(i+1, len(envelopes)):
                # i: len(envelopes)-1 부터 0까지
                # i< j-> len(envelopes)-1 까지
                if(envelopes[i][0] < envelopes[j][0] and envelopes[i][1] < envelopes[j][1]):                    
                    max_lengh = max(max_lengh, call_dp(j)+1)
            return max_lengh

        max_count = 0

        # i: len(envelopes)-1 부터 0까지
        for i in range(len(envelopes)-1, -1, -1):
            max_count = max(max_count, call_dp(i))
        return max_count

 

일부 경우, 여전히 Time Limit Exceeded 으로 인해

-> 이진 탐색으로. 변경

from typing import List

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

        # height 배열 추출
        heights = [h for _, h in envelopes]

        # LIS 계산을 위한 배열
        lis = []

        for h in heights:
            # 이진 탐색으로 위치 찾기
            pos = self.binary_search(lis, h)
            
            if pos == len(lis): 
                # h 가 삽입할 위치가 lis 의 마지막, 즉, lis의 길이와 같다면
                lis.append(h)  # 새로운 값 추가
            else:
                # h 가 삽입할 위치가 lis 내에 이미 있다면, 
                lis[pos] = h  # 기존 값 대체

        return len(lis)

    def binary_search(self, lis: List[int], target: int) -> int:
        """
        LIS 배열에서 target 값을 삽입할 위치를 찾는 이진 탐색 함수

        정확히 하는 역할:
        - LIS 배열에서 주어진 target 값을 삽입할 최초로 크거나 같은 위치를 찾습니다.
        - 이 위치를 삽입 위치라고 합니다.
        - 이 과정은 정렬된 배열에서 이진 탐색을 사용하여 O(log n) 시간에 수행됩니다.

        동작 원리:
        1. 입력:
           - lis: 현재까지 계산된 LIS 배열 (항상 정렬된 상태)
           - target: 현재 처리 중인 height 값
        2. 출력:
           - target을 삽입해야 할 위치 (pos)
        3. 기본 논리:
           - 배열을 절반씩 나누며, lis[mid]와 target을 비교합니다.
           - lis[mid] < target: target이 더 크므로, 오른쪽 구간에서 탐색.
           - lis[mid] >= target: target이 작거나 같으므로, 왼쪽 구간에서 탐색.
        """
        low, high = 0, len(lis)
        while low < high:
            mid = (low + high) // 2
            if lis[mid] < target:
                low = mid + 1  # target이 더 크므로 오른쪽 탐색
            else:
                high = mid  # target이 작거나 같으므로 왼쪽 탐색
        return low  # 삽입 위치 반환

 

from typing import List
from bisect import bisect_left

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # width 오름차순, height 내림차순 정렬
        # Sort by width in ascending order, and by height in descending order
        # 정렬 이유:
        # 1. width는 오름차순으로 정렬하여 가로 길이가 증가하는 순서대로 배치.
        # 2. 같은 width를 가진 경우, height를 내림차순으로 정렬하여 
        #    중첩되지 않도록 만듦 (같은 width에서 height가 증가하면 문제가 생김).
        # Reason for sorting:
        # 1. Sort widths in ascending order to arrange envelopes in increasing width.
        # 2. For envelopes with the same width, sort heights in descending order to
        #    prevent nesting issues (increasing height with the same width causes problems).
        envelopes.sort(key=lambda k: (k[0], -k[1]))

        # height 배열 추출
        # Extract the heights from the sorted envelopes
        heights = [h for _, h in envelopes]

        # LIS 계산을 위한 배열
        # Array to calculate the Longest Increasing Subsequence (LIS)
        lis = []

        for h in heights:
            # bisect_left로 위치 찾기
            # bisect_left:
            # - "주어진 값과 같거나 큰 첫 번째 위치"를 찾음
            # - "Find the first position where the value is greater than or equal to the given value"
            # - 동일한 값이 있는 경우 왼쪽 끝에 삽입함.
            # - "If the same value exists, it inserts at the leftmost position."
            pos = bisect_left(lis, h)
            
            if pos == len(lis): 
                # h 가 삽입할 위치가 lis 의 마지막, 즉, lis의 길이와 같다면
                # If h should be added at the end of lis (same as the length of lis)
                lis.append(h)  # 새로운 값 추가 / Append the new value
            else:
                # h 가 삽입할 위치가 lis 내에 이미 있다면, 
                # If h replaces an existing value in lis
                lis[pos] = h  # 기존 값 대체 / Replace the existing value

        return len(lis)  # LIS 배열의 길이를 반환 / Return the length of the LIS array