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

[hsskey]

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

문제

📝 제약조건

• 제약조건 작성

💡 예시

• Input: input
  • Output: output

문제 해결 과정

Step 1: 문제 이해하기

• 제약조건, input, output을 확인하여 문제를 정확히 파악합니다.

Step 2: 접근 방법

• 직관적으로 생각하기

  • 보통 완전탐색으로 시작
  • 문제 상황을 단순화하여 생각하기
  • 문제 상황을 극한화하여 생각하기

• 자료구조와 알고리즘 활용

  • (1) 문제이해에서 파악한 내용을 토대로 어떤 자료구조를 사용하는 게 가장 적합한지 결정
  • 대놓고 특정 자료구조와 알고리즘을 묻는 문제도 많음
  • 자료구조에 따라 선택할 수 있는 알고리즘을 문제에 적용

• 메모리 사용

  • 시간복잡도를 줄이기 위해 메모리를 사용하는 방법
  • 대표적으로 해시테이블

Step 3: 코드 설계

• 문제의 제약조건과 입력값을 고려하여 효율적인 알고리즘을 설계합니다.

Step 4: 코드 구현

• 설계한 알고리즘에 따라 코드를 작성하고 테스트합니다.

 const fs = require('fs')
 const filePath = process.platform === 'linux' ? '/dev/stdin' : `${__dirname}/input.txt`
 const input = fs.readFileSync(filePath).toString().split('\n')

 const [n, k] = input[0].split(' ').map(Number)
 const arr = input[1].split(' ').map(Number)

 let result = 0
 let eraseCount = 0
 let end = 0
 // start를 고정시키고 end를 증가시키는 형태
 for (let start = 0; start < n; start++) {
    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--
 }
 console.log(result)