[백준1365_자바스크립트(javascript)] - 꼬인 전깃줄

🔴 문제

꼬인 전깃줄

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], A] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const lis = [A[0]];

for (let i = 1; i < n; i++) {
  const target = A[i];

  if (lis.at(-1) < target) lis.push(target);
  else {
    let left = 0;
    let right = lis.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (lis[mid] < target) left = mid + 1;
      else right = mid;
    }

    lis[left] = target;
  }
}

console.log(n - lis.length);

🟢 풀이

⏰ 소요한 시간 : -

이 문제를 읽어보고 예시를 몇개 그려보다 보니 LIS구나...!라는 생각이 들어 알고 있던 dp로 풀이했다.
근데 시간초과 발생. 알고보니 n의 범위가 커서 dp가 아닌 이분탐색으로 풀이해야 한다고 한다.
근데 나는 이분탐색으로 LIS를 풀어본적이 없어 [백준12015_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열 2를 먼저 풀고왔다...
참고로 코드는 가장 긴 증가하는 부분 수열 2이랑 동일하다. 이 문제가 LIS임을 깨닫는게 중요한 것 같다.

🔵 Ref