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

https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/description/?envType=study-plan-v2&envId=dynamic-programming

 

아직도 문제를 직관적으로 해결하지 못하는 것 같다. 한시간만에 풀긴 했으나 아직도 이분탐색의 디테일한 조건처리를 헷갈리는 것 같다.

또한 전형적인 LIS 알고리즘 문제였지만 LIS를 그저 외우기만 할 뿐 활용하는 능력이 없었기에 애를 먹은 것 같다.

 

import java.util.*;
class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int [] answer = new int[obstacles.length];
        int [] dp = new int[obstacles.length];
        int flag = 0;
        for (int i = 0; i < obstacles.length; i++) {
            int left = 0;
            int right = flag;
            int pivot = obstacles[i];
            if(pivot > obstacles[i]) continue;
            while(left < right) {
                int mid = (left+right)/2;
                if (dp[mid]  >  pivot) {
                    right = mid;
                }
                else {
                    left = mid + 1;
                }
            }
            if(left==flag) flag++;
            dp[left] = pivot;            
            answer[i] = left + 1;
        }
        return answer;
    }
}

 

배열을 순회하면서 이분탐색을 통해 해당 순회할 때의 요소의 위치를 찾아주었는데

이 위치가 결국 0부터 해당 인덱스까지의 LIS였다.

 

처음엔 매번 배열을 순회할 때마다 중첩 반복문으로 해당 인덱스전까지 이분탐색으로 계속 LIS 배열을 새로 만들어서 시간초과가 나버렸고
결국 생각해보니 배열을 한 번만 순회하면서 이분탐색으로 인덱스만 정하면 되는 문제였다.

알고리즘 영역에서 정렬된 상태를 사용한다면 꼭 이분탐색을 고민해야 하는 것 같고 또한 메모이제이션의 개념을 어떻게 초기화하여 나타낼 것인가가 dp의 포인트인 것 같다.