백준 12015 - 가장 긴 증가하는 부분 수열 2( Node.js )

백준12015 가장 긴 증가하는 부분 수열 2

이진 탐색(Binary Search)를 사용한 LIS( Longest Increasing Subsequence) 풀이

 

입력값이 1,000,000이 최대이므로 N^2으로는 풀 수 없음 최대 NlogN

이진탐색을 써야하는 문제인 건 알고 있는데 도대체 어디에;;

 

LIS 풀이법을 결국 떠올리지 못하고 해답을 찾아보았다.

새로운 배열을 만들어서 원본 배열 원소와 비교하며 새로운 배열에 차례대로 넣으면 되는 아주 간단한 풀이 방식이였다.

1. LIS를 저장할 배열(lisArr)을 유지하면서 이진 탐색
2. 현재 값이 lisArr의 마지막 값보다 크면 추가
3. 그렇지 않다면, lisArr에서 현재 값이 들어갈 위치를 이진 탐색(lower_bound)을 사용해 찾고 교체
4. 최종적으로 lisArr 배열의 길이가 LIS의 길이(LIS 그 자체가 되는 것은 아님)

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split("\\n").map(v => v.split(' ').map(Number))
const [N] = input[0];
const arr = input[1];
let lisArr = [arr[0]]

for(let i = 1; i< N; i++) {
  let current = arr[i]
	// 현재 값이 LIS의 끝값보다 크면 추가
  if(lisArr[lisArr.length - 1] < current ) lisArr.push(current);
  else{
	// 이진 탐색을 활용해서 들어갈 위치 찾기 (LowerBound)
    let start = 0;
    let end = lisArr.length - 1

    while(start <= end ) {
      let mid = Math.floor((start + end) / 2)
      if(lisArr[mid] >= current) end = mid -1 
      else start = mid + 1 
    }
    lisArr[start] = current // 찾은 위치로 값 덮어씌우기
  }
}

console.log(lisArr.length)

 

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