[75 LeetCode] 23 - Longest Increasing Subsequence

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/longest-increasing-subsequence/submissions/944828649/

역시나 dp이고, 못풀었다.
몇년전에 공부할 때 접한 적 있는 문제임에도, DP는 마땅한 풀이법이 생각나지 않으면 못풀게 된다.

가장 단순한 방식의 DP는 O(n^2)이라 사용하지 않으려했는데, 그거로라도 풀린다니 풀어볼 걸 그랬다.

풀이에서 알려주는 가장 빠른 방식은 O(nlogn)까지 가능하다고 한다.

solution 일부

1. subArray가 비어있으니 첫 값을 넣는다., sub1 = [2].
2. 6은 2보다 크니 들어갈 수 있다. sub1 = [2, 6]
3. 8도 2보다 크니 들어갈 수 있다. sub1 = [2, 6, 8]
4. 3은 현재 sub1에 들어갈 수 없다. 하지만, [2, 3, ...]으로 이어지는 시퀀스가 있을 수 있다. 그래서 저장해둬야한다.
5. sub1 = [2, 6, 8], sub2 = [2, 3]로 저장해둔다.
6. 4는 sub1에는 못들어가지만 sub2에는 들어갈 수 있다. sub1 = [2, 6, 8], sub2 = [2, 3, 4].
    ([2, 4...]는 항상 [2, 3, 4...]보다 작기 때문에 sub를 추가하지 않는다.)
7. 5는 sub1에는 못들어가지만 sub2에는 들어갈 수 있다 sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5].
8. 1은 현재 sub 들에 들어갈 수 없다. 하지만, [1, ...]으로 이어지는 시퀀스가 있을 수 있다. 그래서 저장해둬야한다. sub1 = [2, 6, 8], sub2 = [2, 3, 4, 5], sub3 = [1].
9. 최종결과: len(sub2) = 4.

위 아이디어까지는 떠올랐는데, 구체적으로 실행할 방법이 떠오르지 않았다.
sub들을 어떻게 관리해야하고 어떻게 새 element와 각 sub와 비교를 해야 가장 효율적일까?

가장 단순한 방법: subArrays를 만들고 위 알고리즘처럼 매 반복마다 모든 subArray의 마지막 값과 비교하여 추가해준다.
시간 복잡도가 O(n^2)이라 사용하지 않으려했는데, 그거로라도 풀린다니 풀어볼 걸 그랬다. (n개의 element에 대해, 모든 subArray들 반복, subArray들의 element개수의 총합 <= n이므로 최대 n*n)

여기서 binary search를 사용한다고 한다.
"왜 갑자기 이진트리를 쓰지?" 하는 생각이 드는데, 기억해둬야하는 예시인 것 같다.

subArray를 하나만 두고, 여기에서 새로운 엘리먼트가 들어갈 위치를 이진탐색으로 찾는다.
subArray한 개에 여러 subArray를 겹쳐서 관리하는 느낌이다.

위 예시를 생각해보자.

nums = [2, 6, 8, 3, 4, 5, 1]

1) [2]
2) [2, 6]
3) [2, 6, 8]  <-- sub1이 기록된다. 앞으로 나올 값 중에 8보다 큰 값이 있다면 뒤에 추가될 것이다.
4) [2, 3, 8] <-- 여기서 3이 들어온다. sub1 [2, 6, 8]을 sub2 [2, 3]으로 덮어쓴 형태이다.
    이대로 종료된다고 하면 최대 길이는 sub의 길이인 3이 된다.
    8보다 큰 값이 나오면 어차피 뒤에 붙으니 최대 길이는 정상적으로 늘어난다. 
    8보다 작고 3보다 큰 값이 나오면 그 값이 8을 대체한다.
5) [2, 3, 4] <-- 8이 4로 대체되었다. 어차피 8보다 큰 값이 나오면 [2, 6, 8, 10] [2, 3, 4, 10] 처럼 둘 다 대응이 되기 때문에 대체 돼도 상관이없다.
6) [2, 3, 4, 5] <-- 최대값이 8이었다면 못들어왔을 5도 이렇게 들어올 수 있다.
7) [1, 3, 4, 5] <-- 배열이 더 길다면 맨 앞의 1로 시작하는 subArray가 만들어질 수 있다.
    하지만 여기서 종료돼서 길이에는 영향이 없다.

2  6  8                        <-- sub1
2           3  4  5           <-- sub2
                          1        <-- sub3

sub1, sub2, ... subn을 sub 하나로 관리한다는 아이디어를 떠올리기는 꽤 힘들 것 같다. 기억해 놔야할 것 같다.

 

var lengthOfLIS = function(nums) {
    const sub = [];

    const binarySearch = (val) => {
        let l = 0, r = sub.length;

        while (l < r) {
            const mid = Math.floor((l + r) / 2);

            if (sub[mid] < val) {
                l = mid + 1;
                continue;
            }

            if (sub[mid] >= val) {
                r = mid;
            }
        }

        return l;
    }

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const idx = binarySearch(num);
        sub.splice(idx, 1, num);
    }    

    return sub.length;
};