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

Question

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 인턴 · Answer

안녕하세요, 인프런 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을 넘지 않을 때 최대 길이를 계산합니다. 위 코드를 참고하여 문제를 해결해 보시기 바랍니다.