백준 12015 : 가장 긴 (LIS 알고리즘, 이진탐색) - javascript

문제 출처 

https://www.acmicpc.net/problem/12015

 

정답 풀이 

 

참 좋은 문제이고, 기가막힌 방법이다. 

문제에서 가장 긴 수열 알고리즘의 길이를 구하라고 했으니, 

 

- LIS 알고리즘을 활용하기 

- LIS 알고리즘을 돕는 헬퍼 이진탐색 활용하기 

 

LIS 알고리즘의 푸는 아이디어만 간단하게 공유하면 될 것 같다. 

 

### LIS 알고리즘 

수열 = {10,20,10,30,20,50} 인 경우로 보자. 

 

- 먼저 배열에 10을 넣는다. 

 

 

- 새로 넣어야 하는 수는 20이다 

- 배열의 마지막 값인 10과 비교했을 때 20이 더크니 배열에 추가한다. 

 

 

- 새로 넣어야 하는 수는 10이다

- 배열의 마지막 값인 20과 비교했을 때 10이 더 작다. 

- 배열에서 10보다 크지만 가장 작은 값의 idx를 구한다. 

- 해당 idx 값 대신 10을 넣는다. 

 

위 과정을 반복하는 것이 LIS 알고리즘이다. 

사실 좀 헷갈릴 수 있는데, 

이진탐색을 이용하면, 실제 증가하는 긴 수열을 구하는 것이 아니라 길이만 구할 수 있다. 

 

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const n = Number(input.shift()); 
const arr = input[0].split(' ').map(v => +v)
function solution(n, arr){
    let answer = [arr[0]]; 
   
    for(let i=1; i<n; i++){
        if(answer[answer.length-1] < arr[i]){
            answer.push(arr[i])
        }else{
           let idx = binarySearch(answer, arr[i])
           answer[idx] = arr[i]
        }
    }
    return answer.length; 
    
    //해당 배열에서 target보다 큰데 가장 작은 값 idx를 return 한다. 
    function binarySearch(arr, target){
        let start = 0; 
        let end = arr.length-1; 
        while(start <= end){
            let mid = parseInt((start + end)/2)
            if(arr[mid] < target){
                start = mid +1; 
            }else{
                end = mid-1
            }
        }
        return start
    }
}

console.log(solution(n, arr))