[js] Leetcode 300. Longest Increasing Subsequence

문제

Longest Increasing Subsequence - LeetCode

배열에서 (비연속적으로) 가장 긴 증가하는 순차의 길이를 구하시오.

ex). [0 1 2 3 6 4 5] => 0 1 2 3 4 5 : 5개 

 

plus). 시간 복잡도를 n(log(n))으로도 가능하게 짜시오

 

아이디어

dp 문제인 걸 알고 푸니 좀 보였다.

1. dp 배열을 배열의 길이만큼 만들고 0으로 초기화한다.

2. 배열을 순회하면서 현재 내 위치(i)보다 작은 값들 중 가장 큰 값을 dp배열에서 찾는다.

3. 2번의 값에 + 1을 한 값을 dp 배열에 기록한다.(2번이 없다면 자동으로 1이 되게 설정한다.)

이렇게 하면, 현재 위치에서 가장 긴 배열이 되며 이후에도 이 값을 참조하여 가장 긴 배열이 된다.

 

구현(풀이)

var lengthOfLIS = function(nums) {
    let dp = new Array(nums.length).fill(0)
    let i = 0, maxi =0

    while (i < nums.length) {
        maxi = 0
        for (let j =0; j < i; j++) {
            if((nums[i] > nums[j]) && (dp[j] > maxi)){
                maxi = dp[j]
            }
        }
        dp[i] = maxi +1
       i++
    }

    return Math.max(...dp)
};

1. dp와 i 그리고 maxi 값을 만든다. dp는 해당위치에서 가장 긴 길이를 저장할 것이며, i는 현재 위치, maxi는 i보다 전 배열 중 가장 큰 값을 저장할 변수이다.

2. 반복문을 순회한다. maxi = 0으로 항상 초기화하며 0번째 위치부터 시작한다.

2-2. j <i 를 이용하여 현재 nums 숫자값이 나보다 크고, dp에서 가장 큰 값을 찾아서 maxi 값을 더한다.

2-3. 순회가 끝나면 dp + 1을 기록하고  i를 다음 칸으로 진행시킨다.

3. Math.max 함수를 이용하여 dp값 중 최대값을 찾는다. 

 

남의 풀이

var lengthOfLIS = function(nums) {
    let tails = new Array(nums.length).fill(0)
    let size = 0
    let i = 0
    let j = 0
    for (let k =0; k <nums.length; k++){
        i = 0, j = size
        while (i != j){
            m = parseInt((i + j)/2)
            if (tails[m] < nums[k]){
                i = m + 1
            }
            else {
                j = m
            }
        }
        tails[i] = nums[k]
        size = Math.max(i+1,size)
    }
    return size
};

- 원본 코드를 가져오려다 js로 변경해서 가져왔다. nlog(n) 의 시간복잡도를 가진 코드이다.

1. 각 변수를 선언한다.

- tails : 가장 긴 배열이 될 함수

- size: tails의 실제 사이즈

- i, j : 양 끝으로 0과 size로 시작될 예정

 

2.  i와 j가 다를 시,이분탐색을 진행한다. 이 때, 탐색하는 것은 각 원소가 있어야할 위치이다. 

예를 들어, [2,5,8]인 tails가 있고 다음원소가 4라면 이분탐색으로 5의 index인 1을 찾는다.

그 후, 1의 위치인 인덱스값과 바꾸어 [2,4,8]를 만든다.

만약, 9라면 index는 3으로 [2,5,8,9]가 된다.

 

즉, 이분탐색을 통하여 더 큰 수라면 가장 마지막에 들어가면서 size 자체가 늘어나고, 중앙값이라면 해당하는 위치의 값과 바꾼다.

 

3. 모든 순회가 완료되면 가장 긴 배열이 완성되어있다.

 

참고문서

leetcode 참고풀이 : https://leetcode.com/problems/longest-increasing-subsequence/solutions/74824/java-python-binary-search-o-nlogn-time-with-explanation/