[백준/C++] 알고리즘 22862번 - 가장 긴 짝수 연속한 부분 수열

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 22862번 - 가장 긴 짝수 연속한 부분 수열을 풀어보도록 하겠습니다.

 

 

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

 

 

[문제 접근]

시간 제한이 1초이고 n이 100만이하이기 때문에 O(N) 혹은 O(NlogN) 시간복잡도로 풀어야하는 문제입니다.

연속한 부분 수열을 다루고 있기 때문에 투 포인터로 접근했습니다.

여기서 유의할 점은 

입력이

6 2

2 1 4 4 4 일 때 출력이 3이 나와야하는 점입니다.

 

[풀이 전략]

1. 시작과 끝을 나타내는 변수 st,en을 생성 및 초기화합니다.

2. 삭제 횟수를 세는 cnt를 생성 및 초기화합니다.

3. en <n 일때까지 en을 증가시키는데 만약 arr[en]이 홀수이면 cnt == k면 멈추고  그렇지 않으면 cnt를 증가시킵니다.

4. en -st - cnt로 조건을 만족하는 부분 수열의 길이를 찾은 후 기존에 저장된 부분 수열의 길이와 비교 및 업데이트를 합니다.

5. st가 가리키는 값이 홀수이면 cnt를 1감소시키고 앞으로 1칸 증가시킵니다. 

6. 1~5의 과정을 st<= en을 만족하는 동안에  반복합니다.

 

[코드]

#include <iostream>
#include <algorithm>
using namespace std;


int n, k ; 
int cnt = 0 ;
int arr[1'000'001];
int st = 0 ;
int en = 0  ; 
int answer ; 
int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    cin >> n >> k ;
    for(int i = 0 ; i < n ; i++) cin >> arr[i];

    while(st<= en) {
        while(en < n) {
            if(arr[en] % 2 == 1){
                if(cnt == k) break;
                cnt++;
            }
            en++;
        }  
        answer = max(answer,en-st-cnt);
        
        if(arr[st] % 2 == 1) cnt--;
        st++;

    }
    cout << answer ; 
}

 

[배울 점]

- 정답을 제출하기 전에 항상 예외케이스가 없는지, 내가 푼 코드에 오류가 없는지 생각해보기.  정답을 제출하고 난 다음에는 평정심을 찾기가 쉽지 않음.