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

문제

수열 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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

---

문제풀이

• 주어진 수열에서 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이를 구하는 문제이다.
  • 증가하는 부분 수열: 어떠한 수열의 부분 수열 중 오름차순인 수열을 말한다.
  • 최장 증가 부분 수열(LIS): 증가하는 부분 수열 중 가장 긴 수열을 말한다.
• 해당 문제는 DP를 사용하여 풀이할 수 있다. DP를 사용하면 각 원소까지의 LIS 길이를 저장하면서 배열을 순회하면서 최장 부분 수열의 길이를 계산할 수 있다. (즉, 이전 단계의 계산 결과를 저장하고 활용하여 빠르게 최적해를 찾을 수 있다)
• 아래 코드에서 lis 배열은 현재까지의 LIS를 저장하는 배열이다. 원소를 하나씩 순회하면서 현재 원소(arr[i])가 lis의 마지막 원소보다 크다면 그대로 추가한다. 그렇지 않다면 이진 탐색을 사용하여 lis 배열에 삽입할 위치를 찾는다.
• 이진 탐색을 사용하여 LIS 배열을 업데이트하면 시간 복잡도 O(N*log(N))으로 해결할 수 있다.

✅ 답안

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const arr = input[1].split(' ').map(Number);
const lis = [arr[0]]; // LIS를 저장하는 배열 초기화

for (let i = 1; i < N; i++) {
  if (arr[i] > lis[lis.length - 1]) {
    // 현재 원소가 LIS의 마지막 원소보다 크면 추가
    lis.push(arr[i]);
  } else {
    // 아니라면 이진 탐색을 사용하여 적절한 위치에 삽입
    let start = 0;
    let end = lis.length - 1;
    while (start < end) {
      const mid = Math.floor((start + end) / 2);
      if (lis[mid] < arr[i]) {
        start = mid + 1;
      } else {
        end = mid;
      }
    }
    lis[end] = arr[i];
  }
}
console.log(lis.length);