[최대 길이 연속부분수열] 틀린 이유

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr) {
        int lt = 0, sum = 0, max = 0, count = 0;
        for(int rt = 0; rt < n; rt++) {
            if(arr[rt] == 1) {
                sum += arr[rt];
            } else if (arr[rt] == 0) {
                if(count++ < m) {
                    sum += 1;
                } else {
                    if (sum >= max) {
                        max = sum;
                        sum = 0;
                        lt ++;
                        rt = lt;
                        count = 0;
                    }
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.print(T.solution(n, m, arr));
    }
}

논리적으로 틀린건 없는거 같고, 예시코드도 틀린게 없는데 왜 오답이 나오는지 모르겠습니다 !!

안녕하세요, 인프런 AI 인턴입니다.

Park Jiho님, 제시하신 코드를 살펴보았습니다.
코드에는 논리적 오류가 있습니다. 0을 만날 때 count가 m보다 작다면 sum에 1을 더해주시고, 그렇지 않은 경우 max 값을 갱신한 후 sum을 0으로 초기화하고 lt와 rt를 조절하는 부분에서 문제가 발생합니다. 이부분에서 오류가 있는 것으로 보입니다.

올바른 투 포인터 알고리즘 접근법은 다음과 같습니다:
1. 연속된 0의 개수가 m을 넘지 않도록 유지하면서 rt 포인터를 오른쪽으로 이동합니다.
2. 연속된 0의 개수가 m을 초과하면 lt를 오른쪽으로 이동시키면서 연속된 0의 개수가 다시 m이하가 될 때까지 조정합니다.
3. 이 과정에서 rt - lt + 1 (현재 연속 부분 수열의 길이)의 최댓값을 갱신합니다.

아래는 수정된 코드의 예시입니다:

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr) {
        int answer = 0, cnt = 0, lt = 0;
        for (int rt = 0; rt < n; rt++) {
            if (arr[rt] == 0) cnt++;
            while (cnt > m) {
                if (arr[lt] == 0) cnt--;
                lt++;
            }
            answer = Math.max(answer, rt - lt + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.print(T.solution(n, m, arr));
    }
}

이 코드는 lt 포인터가 rt 포인터를 따라가며 연속된 수열 중 0의 개수가 m을 넘지 않을 때 최대 길이를 계산합니다.

위 코드를 참고하여 문제를 해결해 보시기 바랍니다.

인프런 커뮤니티 질문&답변