[BaekJoon 22857번] 가장 긴 짝수 연속한 부분 수열 (small) (C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

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

 

 

[문제 설명]

 

 

길이가 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번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

 

[제한]

 

•  1 ≤ N ≤ 50,000 
•  1 ≤ K ≤ 100 
•  1≤ 원소의 값 ≤10^6 

 

 

[입출력 예]

 

 

입력	출력
8 2 1 2 3 4 5 6 7 8	3

 

 

[문제 풀이]

 

 

투 포인터 알고리즘을 사용하여 코드를 작성해야 한다.

 

두개의 각 포인터가

 

• 홀수이면 oddcnt(홀수의 개수) 변수를 + 1 증가시킨다.
• 짝수이면  eventcnt(짝수의 개수) 변수를 +1 증가시킨다.

 

K개까지 홀수를 지울 수 있기 때문에 홀수의 개수가 K + 1까지 while문을 반복한다.

K + 1 까지 반복하는 이유는

예를 들어 2개의 홀수를 지울 수 있다면 3개의 홀수를 지우기 이전의 짝수 부분 수열까지 구해야하기 때문이다.

 

그리고 max 함수를 이용해 가장 긴 길이(evencnt 짝수의 개수)를 구하면 된다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>

using namespace std;
vector<int> v;

bool isCheck(int num) {
    if(num % 2 == 0) return true;
    else return false;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; int K; cin >> N >> K;
    v.emplace_back(0);
    for(int i = 0; i < N; ++i) {
        int num; cin >> num;
        v.emplace_back(num);
    }
    int maxLen = 0;
    for(int start = 1; start <= N; ++start) {
        int end = start + 1;
        int oddcnt = 0; // 홀수 개수
        int evencnt = 0;
        if(!isCheck(v[start])) oddcnt += 1;
        else evencnt += 1;

        while(end <= N) {
            if(!isCheck(v[end])) {
                oddcnt += 1;
                if(oddcnt > K) {
                    oddcnt -= 1;
                    break;
                }
            } else {
                evencnt += 1;
            }
            end += 1;
        } 
       
        maxLen = max(maxLen, evencnt);
    }
    cout << maxLen;
    return 0;
}