투 포인터 문제풀이2(가장 긴 짝수 연속한 부분 수열 (large)(22862)

2. 가장 긴 짝수 연속한 부분 수열 (large)(22862)

https://www.acmicpc.net/problem/22862

문제

길이가 N인 수열 S가 있다. 수열 S는 1 이상인 정수로 이루어져 있다.

수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제를 할 수 있다.

예를 들어, 수열 S가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 S에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 S를 구성하고 있는 N개의 수가 공백으로 구분되어 주어진다.

출력

수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

내가 작성한 코드 → 시간초과

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const [n, k] = input[0].split(" ").map(Number); // n: 수열 S의 길이, k: 삭제 최대 횟수
const s = input[1].split(" ").map(Number); // 수열 S

let maxCnt = 0;
let end = 0;
let start = 0;

// 맨 앞 요소가 홀수인 경우 start, end 위치 변경
if (s[0] % 2 !== 0) {
  start += 1;
  end += 1;
}

for (; start < n; start += 1) {
  let cnt = 0;
  let deleteCnt = k; // 삭제 횟수 초기값으로 설정
  end = start;
  // 삭제 횟수가 남아있을 경우
  while (deleteCnt >= 0) {
    // 홀수 만난 경우
    if (s[end] % 2 !== 0) {
      deleteCnt -= 1; // 삭제 횟수 감소
    } else cnt += 1;
    end += 1; // 끝점 이동
  }
  maxCnt = Math.max(maxCnt, cnt);
}
console.log(maxCnt);

• 삭제 횟수가 줄어들지 않는 경우 고려 안함!
  • 이 경우, end가 n을 넘어버리는 문제 발생

풀이 코드

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");

const [n, k] = input[0].split(" ").map(Number); // n: 수열 S의 길이, k: 삭제 최대 횟수
const arr = input[1].split(" ").map(Number); // 수열 S

let result = 0;
let eraseCount = 0;
for (let start = 0, end = 0; start < n; start += 1) {
  while (end < n) {
    if (arr[end] % 2 == 0) end += 1; // 짝수인 경우 end 증가
    else {
      if (eraseCount == k) break; // 더 지울수 없다면 종료
      // 지울 수 있는 여건이 있다면 지우기
      eraseCount += 1;
      end += 1;
    }
  }
  result = Math.max(result, end - start - eraseCount); // 범위의 길이 계산
  // start를 한 칸 오른쪽 이동할 때, 가능하다면 지울 수 있는 개수 증가
  if (arr[start] % 2 == 1) eraseCount -= 1;
}
console.log(result);

풀이

• 짝수인 경우: 단순히 end를 오른쪽으로 이동
• 홀수인 경우: 최대 K까지 end를 오른쪽으로 이동