LeetCode #1964 Find the Longest Valid Obstacle Course at Each Position

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #1964 Find the Longest Valid Obstacle Course at Each Position

문제 풀이

LIS(Longest Increasing Subsequence) 문제와 유사해서 시도해봤으나 결국 해결하지 못해 주간 LeetCode 챌린지 3솔에서 끝나고 말았다. 풀이를 보아하니 경험하지 못하면 못 풀 듯하지만 다시 비슷한 문제를 보게 된다면 그방 풀어낼 수 있을 듯하다. 이진 탐색을 이용한 LIS는 bisect_left를 사용해 자신과 같거나 큰 좌표를 이용했으나 이번에는 bisect_right를 사용해 무조건 자신보다 큰 값들 중 최소값 좌표를 풀이에 사용해야 한다.

• lis 배열을 생성
• 첫 번째 원소부터 마지막 원소까지 순회를 진행하되 만약 lis 배열이 비어있거나 lis 배열의 마지막 원소 이상이라면 그대로 lis 배열에 삽입하고 해당 좌표의 답을 lis 배열의 길이로 저장한다.
• 만약 탐색 좌표의 값이 lis 배열의 마지막 값 이하라면 우선 탐색 좌표의 값보다 큰 값이 처음으로 등장하는 lis 배열에서의 좌표를 구한다.(Binary Search에서의 Upper Bound, bisect 모듈의 bisect_right 함수 사용)
• lis 배열에 앞서 구했던 좌표의 값을 갱신하고 해당 좌표의 정답을 Upper Bound 좌표 + 1로 저장한다. (0 좌표이기 때문)

python 코드

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        lis = []
        for i, x in enumerate(obstacles):
            if not lis or x >= lis[-1]:
                lis.append(x)
                obstacles[i] = len(lis) + 1
            else:
                idx = bisect.bisect_right(lis, x)
                lis[idx] = x
                obstacles[i] = idx + 1
        return obstacles