[BOJ 12738] 가장 긴 증가하는 부분 수열 3

문제

가장 긴 증가하는 부분 수열 3

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

 

 

풀이

설명

LIS(가장 긴 증가하는 부분 수열)의 길이를 구하는 문제입니다.

 

이분탐색을 이용해 해결할 수 있습니다.

수열을 순회하면서 이분탐색을 이용해 해당 숫자를 lis의 적절한 위치에 넣으면 됩니다.

 

예시 코드

function solution() {
  const N = +input();
  const A = input().split(" ").map(Number);
  const lis = [A[0]];

  for (let i = 1; i < N; i++) {
    if (A[i] < lis[0]) lis[0] = A[i];
    else if (A[i] > lis[lis.length - 1]) lis.push(A[i]);
    else {
      let low = 0,
        high = lis.length - 1;

      while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        if (lis[mid] >= A[i]) high = mid - 1;
        else low = mid + 1;
      }

      lis[low] = A[i];
    }
  }

  return lis.length;
}