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

상현·2023년 11월 16일

LIS 백준 코딩테스트

코딩테스트

목록 보기

19/30

[Gold II] 가장 긴 증가하는 부분 수열 2 - 12015

문제 링크

성능 요약

메모리: 139204 KB, 시간: 620 ms

분류

이분 탐색, 가장 긴 증가하는 부분 수열: O(n log n)

제출 일자

2023년 11월 16일 11:27:11

문제 설명

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

최종 제출

var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().split('\n');

const N = +input.shift();
const array = input[0].split(' ').map(Number);

let lis = [array[0]];

// 이분 탐색으로 배열에서 가장 num과 가까운 수를 찾는다.
const findClose = (start, end, num) => {
  
  // 끝 포인터가 시작 포인터보다 커지면 종료
  while (start < end) {
    
    // 중간 인덱스와 값
    let mid = Math.floor((start + end) / 2);
    const midValue = lis[mid];

    
    if (midValue >= num) {
      // 중간 값보다 num이 작으면 끝 포인터를 줄여서 다시 검색한다.
      end = mid;
    } else {
      // 중간 값보다 num이 크면 시작 포인터를 키워서 다시 검색한다.
      start = mid + 1;
    }
  }

  return start;
};

for (let i = 1; i < array.length; i++) {
  let num = array[i];
  let peek = lis[lis.length - 1];

  
  if (num > peek) {
    // LIS 배열의 끝 요소가 새로 들어오는 것보다 작으면 그냥 넣는다.
    lis.push(num);
  } else {
    // 아니면 새로 들어온 요소와 가장 가까운 숫자를 찾아 교체 해준다.
    let closeIndex = findClose(0, lis.length - 1, num);

    lis[closeIndex] = num;
  }
}

// 결국에는 가장 큰 길이의 수열이 남게 된다.. (값 X, 길이만)
console.log(lis.length);