백준 22862 JAVA : 가장 긴 짝수 연속한 부분 수열 (large)

문제

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

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

 

풀이 예상

투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다.

짝수의 길이 = endPoint - startPont - 홀수의 개수

 

풀이방법 (접근 방법 & 시간복잡도)

1. isOdd[] 배열에 홀수면 true, 짝수면 false 를 넣어준다.

2. count (홀수의 개수 카운트) 가 K 번 나올 때 까지 endPoint를 늘려준다.

3. count가 K개 이고, 다음 숫자가 짝수인 경우 endPoint를 +1해준다.

4. count가 K개이고, 다음 숫자가 홀수인 경우 startPoint를 +1해준다.

5. endPoint가 늘어날 때 마다 값을 갱신해준다.

 

예제를 예시로 들어보면,

8 2
1 2 3 4 5 6 7 8

 

1. 초기 세팅

startPoint, endPoint = 0, count = 0, answer = 0

 

2. while문 - 1

count = 1, startPoint = 0, endPoint = 1, answer = 0(1-0-1)

 

3. while문 - 2

count = 1, startPoint = 0, endPoint = 2, answer = 1(2-0-1)

 

3. while문 - 3

count = 2, startPoint = 0, endPoint = 3, answer = 1(3-0-2)

 

4. while문 - 4

count = 2, startPoint = 0, endPoint = 4, answer = 2(4-0-2)

 

5. while문 - 5

count = 1, startPoint = 1, endPoint = 4, answer = 2(4-1-1)

 

6. while문 - 6

count = 1, startPoint = 1, endPoint = 5, answer = 3(5-1-1)

 

...

 

위의 로직대로 코드를 짜면 아래와 같다.

 

시간복잡도 => O(N)

startPoint와 endPoint는 한번의 반복으로 최대 N까지 이동한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean[] isOdd = new boolean[N]; //홀수면 true, 짝수면 false

        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(num%2 == 1) {
                isOdd[i] = true;
            }
        }


        int count = 0; //홀수 개수 카운트
        int startPoint = 0;
        int endPoint = 0;
        int answer = 0;

        while(true) {
            if(count < K) {
                //K까지 늘림
                if(isOdd[endPoint]) {
                    count++;
                }
                endPoint += 1;
                answer = Math.max(answer, endPoint - startPoint - count);

            } else if(!isOdd[endPoint]) {
                //count == K, 짝수일 경우
                endPoint += 1;
                answer = Math.max(answer, endPoint - startPoint - count);

            }else {
                //count 가 K를 넘는 경우, count==K && 뒤가 바로 홀수 인경우
                //앞 숫자를 떙김
                if(isOdd[startPoint]) {
                    count--;
                }
                startPoint += 1;

            }
            if(endPoint == N) {
                break;
            }

        }

        System.out.println(answer);

    }
}

 

결과