🔴 문제
🟡 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(lis.length);
🟢 풀이
⏰ 소요한 시간 : -
가장 긴 증가하는 부분 수열 LIS 유형이다.
이 문제는 n의 범위에 따라 풀이 방법이 달라지는데 가장 긴 증가하는 부분 수열의 경우 n의 범위가 1,000이기에 시간복잡도가 O(n^2)인 dp로 풀이할 수 있다.
하지만 가장 긴 증가하는 부분 수열 2같은 경우에는 n의 범위가 1,000,000이다. dp로 풀이 시 O(n^2)의 시간복잡도로는 1,000,000,000,000의 연산을 해야되고 이는 1초안에 불가능하다.
따라서 이분탐색을 도입해 LIS풀이를 한다.
이 문제의 포인트는 정답 수열의 각 요소를 정확하게 구하지 않아도 되고, 길이만 구하면 되는것이다.
예제를 통해 예시를 들어보자.
설명을 편하게 하기 위해 A수열을 살짝 바꿔봤다.
A = [10, 20, 10, 15, 17, 50]lis 배열을 하나 만들어 A수열의 첫 요소를 넣어준다.
lis = [10]그럼 10다음인 20부터 즉 i는 1부터 n-1까지 순회를 하며 배열의 모든 요소를 lis에 넣을 지 말 지 정해주면 된다.
수열에서 현재 탐색중인 요소를 target이라고 하자.
lis의 가장 마지막 요소가 target보다 작으면 lis배열에 target을 넣어준다.
lis = [10, 20]그러면 위와 같이 될 것이다. 그 다음 요소인 15은 lis 수열의 가장 마지막 요소인 20보다 크지 않다.
따라서 이 경우에는 lis를 탐색하며 값을 바꿔줄 요소를 찾는다.
lis가 [10, 20] 일 때보다 [10, 15]로 업데이트 해주어야 그 다음에 올 17을 lis에 추가할 수 있기 때문이다.
이 과정을 이분탐색으로 구현한다.
left를 0번 인덱스, right 를 lis 배열의 마지막 인덱스로 두고 중간인덱스 mid를 구한 뒤 lis배열의 mid값을 갱신해준다.
더 자세한 풀이는 아래의 참고자료에서 볼 수 있다.
🔵 Ref
