[개발일지] - 467(주말)

(1).백준 12738번 가장 긴 증가하는 부분 수열 3는 음수가 들어갈 뿐 2번과 동일한 문제였고

테스트케이스들을 수정해봤지만 이전과 동일한 방식으로 당연히 처리가 잘 되는 것이 확인되었고

동일하게 들어오는 값의 올바른 순서에 최소값을 집어넣어주고

그 다음 값들을 순차적으로 추가해서 최대 길이를 출력하는 방식으로 해결했다.

const input = `8
10 30 -40 20 -25 -30 35 40`.split('\n')[1].split(' ').map(Number)

const arr = []

for(let i = 0 ; i < input.length ; i++){
    let low = 0
    let high = arr.length

    while(low < high){
        let mid = Math.floor((low + high)/2)
        if(arr[mid] < input[i]){
            low = mid + 1
        } 
        else{
            high = mid
        }
    }

    if(low < arr.length){
        arr[low] = input[i]
    }
    else{
        arr.push(input[i])
    }
}

console.log(arr.length)