1964. Find the Longest Valid Obstacle Course at Each Position ★★★

1964. Find the Longest Valid Obstacle Course at Each Position

 

from typing import List
import bisect

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        # LIS 구하는데, 단, 같아도 됨, <= 만족하게.
        # Finding LIS (Longest Increasing Subsequence) where "less than or equal to" is allowed.
        # hard 니깐.. 속도 문제. BST 이진 탐색 사용해야 함
        # As this is a hard problem, we need to optimize using binary search.
        
        res  = [] # 결과 배열 / Result array
        lis = [] # LIS 배열 / LIS array
        # lis는 항상 정렬된 상태로 유지되며, 각 장애물을 삽입하거나 대체하여 LIS 조건을 만족
        # The LIS array is always maintained in sorted order and satisfies the LIS condition by inserting or replacing elements.
        
        for obstacle in obstacles:
            # 이진 탐색으로 삽입 위치 찾기: bisect_right를 사용하여 "같거나 큰 위치"를 찾습니다.
            # Find the position to insert using binary search: bisect_right finds the "position where the value is greater than or equal."
            """
            bisect_right:
            - "주어진 값을 초과하는 첫 번째 위치"를 찾음
            - "Finds the first position exceeding the given value."
            - 현재 값보다 같거나 큰 값을 허용하고, 동일한 값이 있는 경우 오른쪽 끝에 삽입
            - "Allows values greater than or equal to the current value, inserting at the rightmost position if the same value exists."

            bisect_left:
            - "주어진 값과 같거나 큰 첫 번째 위치"를 찾음
            - "Finds the first position equal to or greater than the given value."
            - 동일한 값이 있는 경우 왼쪽 끝에 삽입합니다.
            - "If the same value exists, inserts at the leftmost position."

            이 문제에서 장애물의 순서는 "같거나 더 커야 한다"는 조건을 만족해야 함
            This problem requires the order of obstacles to satisfy the condition "equal or greater."
            따라서:
                1) 같은 값 허용:
                    동일한 높이의 장애물이 존재하는 경우, 
                    bisect_right는 오른쪽에 삽입하여 다음 값이 더 크거나 같은 값을 허용함
                2) 길이 계산:
                    pos 값은 "현재 장애물을 포함했을 때, 장애물 코스에서의 위치"를 나타냄
                    bisect_right를 사용하면, 같은 값을 중첩하여 더 긴 경로를 만들 수 있음
                1) Allow same values:
                    If an obstacle with the same height exists,
                    bisect_right inserts it on the right, allowing the next value to be greater or equal.
                2) Length calculation:
                    The pos value represents the "position in the obstacle course including the current obstacle."
                    Using bisect_right allows nesting of the same value, creating longer paths.
            """
            pos = bisect.bisect_right(lis, obstacle)

            if pos == len(lis): # pos 가 lis 길이가 같으면,
                # If pos equals the length of lis,
                lis.append(obstacle) # lis 에 추가 / Append to lis
            else:
                lis[pos] = obstacle # 기존 값을 대체 / Replace the existing value

            """
            현재 위치까지의 최대길이를 결과에 추가
            - 경로 길이는 1부터 시작
            - 하지만 이진 탐색은 0부터 시작하는 인덱스를 반환하므로, 
            - 실제 길이를 계산하려면 +1이 필요합니다.
            Add the maximum length up to the current position to the result.
            - The path length starts from 1.
            - However, binary search returns an index starting from 0,
            - so to calculate the actual length, +1 is required.
            """
            res.append(pos+1) 
        return res

 

 

 

https://youtu.be/Xq9VT7p0lic?si=SPzorVE4gw3o4RNY