23.05.07. 풀었던 문제들

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

 일단 이 문제는 i까지 진행하면서 모든 obstacles에 대해 longest course length를 저장하면 될 것 같은 문제이다. 이 때, 각 course는 obstacles[i]부터 i = 0까지 내림차순으로 진행되어야 하며 i는 꼭 포함되어야 한다. 어디서 많이 본 접근 아닌가? 바로 LIS이다.

 예전에 작성했던 DP + LIS 포스팅, lower bound & upper bound 포스팅 그대로 풀면 될 것이다. 단, 대신, 기존 LIS는 strictly increasing인 반면 이 문제는 monotinic increasing이다. 이를 고려해서 문제를 풀어야 한다. 즉슨, LIS.back() < cur 부분의 로직은<=로 바뀌어야 할 것이고, lower_bound로 찾았던 부분은 [2, 3, 4]와 같이 만들어져 있는 상황에서 3을 넣는다고 할 때, 기존의 3을 바꾸는 것이 아니라(lower bound로 찾기), 3보다 큰 수 중 가장 작은 수인 4를 3으로 바꿔야 하므로 upper bound를 찾아야 한다.

// Runtime 315 ms Beats 60.42%
// Memory 117.7 MB Beats 69.44%

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<int> answer(n), LIS;

        LIS.push_back(obstacles[0]);
        answer[0] = 1;
        for(int i = 1; i<n; i++){
            if(LIS.back() <= obstacles[i]){ // LIS 늘이는 경우
                LIS.push_back(obstacles[i]);
                answer[i] = LIS.size();
            }
            else{ // 중간에 넣을 수 있는 경우
                int start = 0, end = LIS.size()-1; // upper bound
                while(start < end){
                    int mid = (start + end) / 2;
                    if(obstacles[i] < LIS[mid]){ // 앞으로 당김 *** 실수 : LIS[mid]가 아니라 obstacles[mid]를 해 버렸다.
                        end = mid;
                    }
                    else{
                        start = mid + 1;
                    }
                }        
                // end = upper_bound(LIS.begin(), LIS.end(), obstacles[i]); 
                LIS[end] = obstacles[i];
                answer[i] = end + 1;
            }
        }
        return answer;
    }
};

 

시간복잡도

 upper bound를 사용하는 LIS이므로 O(nlogn)이다.

 

공간복잡도

 worst case O(n) size만큼 LIS 배열에 들어갈 수 있으므로 O(n)이다.