백준 2526 전깃줄

문제

제한 사항

첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.

입출력 예

풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const binarySearch = (list, left, right, target) => {
  while (left < right) {
    let mid = Math.floor((left + right) / 2);

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

const sol = (input) => {
  const n = +input.shift();
  const arr = input
    .map((e) => e.split(" ").map(Number))
    .sort((a, b) => a[0] - b[0]);

  const lis = [];
  lis.push(arr[0][1]);
  for (let i = 1; i < n; i++) {
    if (lis[lis.length - 1] < arr[i][1]) {
      lis.push(arr[i][1]);
    } else {
      let idx = binarySearch(lis, 0, lis.length - 1, arr[i][1]);
      lis[idx] = arr[i][1];
    }
  }

  return n - lis.length;
};

console.log(sol(input));

lis 알고리즘.

첫번째 전봇대를 기준으로 정렬하고, 두번째 기준 lis를 구한다음 전체 길이에서 빼준다.