첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 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를 구한다음 전체 길이에서 빼준다.