백준 / 투 포인터 / 22862번 / 가장 긴 짝수 연속한 부분 수열 (large) / JS
문제 간단설명
길이가 N인 수열 S가 있다.
수열 S는 1이상 정수로 이루어져 있는데,
최대 K개의 정수를 삭제할 수 있다.
최대 K개 삭제한 수열에서,
짝수로 이루어져 있는 연속한 부분 수열 중,
가장 긴 길이를 구하면 된다.
제한 사항
- 1 <= N <= 1,000,000
- 1 <= K <= 100,000
- 1 <= 원소의 값 <= 1,000,000
성공 코드
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : '../input.txt';
// const filePath = process.platform === 'linux' ? '/dev/stdin' : 'BOJ/input.txt';
const input = fs
.readFileSync(filePath)
.toString()
.trim()
.split('\n')
.map((el) => el.trim());
const [N, K] = input.shift().split(' ').map(Number);
const sequence = input.shift().split(' ').map(Number);
function solution() {
let left = 0;
let right = 0;
let removeCount = 0; // 제거한 홀수의 개수
let result = 0;
while (right < N) {
// 짝수일 경우
if (sequence[right] % 2 === 0) {
result = Math.max(result, right - left - removeCount + 1);
right++;
} else {
// 홀수일 경우
// 제거한 홀수의 개수가 K보다 작으면 제거한 홀수의 개수를 증가시키고 포인터를 오른쪽으로 이동
if (removeCount < K) {
removeCount++;
right++;
} else {
// 더 이상 제거할 수 없으면 왼쪽 포인터를 오른쪽으로 이동
while (removeCount === K) {
// 왼쪽 포인터가 가리키는 수가 홀수일 경우
// 제거한 홀수의 개수를 줄이고 왼쪽 포인터 한 칸 오른쪽으로 이동
if (sequence[left] % 2 === 1) {
removeCount--;
}
left++;
}
}
}
}
console.log(result);
}
solution();
투 포인터 알고리즘에서 조금 더 응용이 들어간 문제였다.
기본적인 문제에서 다음 두 가지만 신경쓰면 된다.
- 제거 횟수 관리
- 더 이상 제거할 수 없을 때 어떻게 할것인지
제거 횟수 관리
먼저, 제거 횟수를 관리하는 부분부터 알아보자.
처음에 최대 제거 횟수 K가 주어진다.
우리는 이 횟수를 홀수를 제거하는데 써야한다.
오른쪽 포인터가 수열의 끝에 다다를 때 까지 반복문으로 탐색한다.
오른쪽 포인터가 가리키는 값이 짝수라면,
현재 저장되어 있는 최댓값과
현재 수열의 길이에서 제거한 수를 뺀만큼의 길이를 비교하면 된다.
그리고 오른쪽 포인터를 한 칸 옮겨준다.
만약 오른쪽 포인터가 가리키는 값이 홀수라면,
다음 두 가지 상황이 있다.
- 제거할 수 있는 횟수가 남았을 때
- 제거할 수 있는 횟수가 남지 않았을 때
제거할 수 있는 횟수가 남았을 때는 간단하다.
현재 가리키는 홀수를 제거하고,
포인터를 한 칸 옮겨주면 된다.
더 이상 제거할 수 없을 때 어떻게 할 것인지
그런데,
제거할 수 있는 횟수가 남지 않았을 때는 어떻게 할까?
일단 왼쪽 포인터를 짝수를 만날때까지 옮겨준다.
그러면 우리가 홀수를 제거할 때 썼던 횟수를 충전할 수 있다.
예시로 알아보자.
1, 2, 4, 4, 5, 6, 7, 8 이라는 수열이 있을 때,
현재 left가 1을 가리키고 있고,
right가 5를 가리키고 있다고 해보자.
'가장 긴 짝수 연속한 부분 수열'을 구해야 하므로,
1을 제거하는데 제거 횟수를 한 번 썼을 것이다.
그러니까 이 때 사용한 제거 횟수를 충전하기 위해서
left를 2로 옮겨준다.
그러면 1, 2, 4, 4, 5 에서 가장 긴 짝수 연속한 부분 수열이나,
2, 4, 4, 5에서 가장 긴 짝수 연속한 부분 수열은 같다.
다만, 전자는 제거 횟수를 1을 제거하는데에 썼고,
후자는 제거 횟수를 사용하지 않았다.
이런 식으로 계속해서 반복하다면,
단 한번의 순회로 문제를 해결할 수 있다.
시간 복잡도는 O(n)이 되는 것이다.