백준 / 투 포인터 / 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();

 

투 포인터 알고리즘에서 조금 더 응용이 들어간 문제였다.

기본적인 문제에서 다음 두 가지만 신경쓰면 된다.

1. 제거 횟수 관리
2. 더 이상 제거할 수 없을 때 어떻게 할것인지

 

제거 횟수 관리

먼저, 제거 횟수를 관리하는 부분부터 알아보자.

처음에 최대 제거 횟수 K가 주어진다.

우리는 이 횟수를 홀수를 제거하는데 써야한다.

 

오른쪽 포인터가 수열의 끝에 다다를 때 까지 반복문으로 탐색한다.

 

오른쪽 포인터가 가리키는 값이 짝수라면,

현재 저장되어 있는 최댓값과

현재 수열의 길이에서 제거한 수를 뺀만큼의 길이를 비교하면 된다.

그리고 오른쪽 포인터를 한 칸 옮겨준다.

 

만약 오른쪽 포인터가 가리키는 값이 홀수라면,

다음 두 가지 상황이 있다.

1. 제거할 수 있는 횟수가 남았을 때
2. 제거할 수 있는 횟수가 남지 않았을 때

제거할 수 있는 횟수가 남았을 때는 간단하다.

현재 가리키는 홀수를 제거하고,

포인터를 한 칸 옮겨주면 된다.

 

더 이상 제거할 수 없을 때 어떻게 할 것인지

그런데,

제거할 수 있는 횟수가 남지 않았을 때는 어떻게 할까?

 

일단 왼쪽 포인터를 짝수를 만날때까지 옮겨준다.

그러면 우리가 홀수를 제거할 때 썼던 횟수를 충전할 수 있다.

예시로 알아보자.

 

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)이 되는 것이다.