[JS][백준]22857_가장 긴 짝수 연속한 부분 수열 (small).

문제 번호

22857번: 가장 긴 짝수 연속한 부분 수열 (small)

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 브루트포스 알고리즘
• 두 포인터

 

문제 풀이

 투 포인터를 사용해서 모든 경우의 수를 찾아보는 문제이다.

투 포인터를 사용하는데 편리하게 하기 위해서 nums라는 배열에 0이라는 의미 없는 숫자를 추가해주었다. 투 포인터의 start와 end는 이 '0'을 가리키면서 시작한다.

const nums = [0];

이후 배열의 숫자가 짝수인경우 'sum'이라는 변수를 1개씩 늘려가면서 연속된 짝수가 몇 개인지 파악한다.

    if (nums[end] % 2 === 0) {
      sum++;
    }

반대로 홀수가 나왔을경우 'cnt'라는 변수를 1씩 늘려가면서 문제에서 주어진 K번만큼 잘랐는지 확인한다.

 else {
      cnt++;
    }

 K번 만큼 홀수가 등장하여서 K번 자르기를 모두 사용했는데, 다시 홀수가 등장한다면 지금까지 K번 자르기를 사용하여  만들 수 있는 ' 가장 긴 짝수 연속한 부분 수열'의 길이는 몇인지 파악한다. 그리고 start의 위치를 다음 홀수의 위치로 옮겨주고, 옮기면서 마주치는 짝수의 개수만큼 sum에서 제외해준다.

 0 2 2 2 '3' 3 2 2 3 이라는 배열의 '0'에서 첫 번째 '3'까지 이동하면서 마주치는 '2'는 3개이다. 그러므로 sum에서 '2'의 개수인 '3'을 빼준다.

 이후 사용한 홀수가 1개 줄었으니 cnt역시 '1' 줄여준다. 

    if (cnt === K && nums[end] % 2 !== 0) { // 다썻는데 또 홀수 만났을때 계산.
      if (sum > answer) answer = sum;
      start++;
      while (nums[start] % 2 === 0) {
        sum--;
        start++;
      }
      cnt--;
    }

 마지막으로 end 포인터가 배열의 끝에 도달했을때를 확인해준다.

    if (end === N && cnt <= K) {
      if (sum > answer) answer = sum;
    }

 

전체 코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split('\n');
const [N, K] = input[0].split(' ').map(Number);
const nums = [0];

function sol() {
  let answer = 0;

  let temp = input[1].split(' ').map(Number);
  for (let i = 0; i < N; i++) {
    nums.push(temp[i]);
  }

  let start = 0;
  let cnt = 0, sum = 0;
  for (let end = 1; end <= N; end++) {
    if (cnt === K && nums[end] % 2 !== 0) { // 다썻는데 또 홀수 만났을때 계산.
      if (sum > answer) answer = sum;
      start++;
      while (nums[start] % 2 === 0) {
        sum--;
        start++;
      }
      cnt--;
    }
    if (nums[end] % 2 === 0) {
      sum++;
    } else {
      cnt++;
    }
    if (end === N && cnt <= K) {
      if (sum > answer) answer = sum;
    }
  }

  console.log(answer);
}

sol();

특이사항