[복합적 문제] 6.최대 길이 연속부분수열

6. 최대 길이 연속부분수열

 

설명

0과 1로 구성된 길이가 N인 수열이 주어집니다. 여러분은 이 수열에서 최대 k번을 0을 1로 변경할 수 있습니다. 여러분이 최대 k번의 변경을 통해 이 수열에서 1로만 구성된 최대 길이의 연속부분수열을 찾는 프로그램을 작성하세요.

만약 길이가 길이가 14인 다음과 같은 수열이 주어지고 k=2라면

1 1 0 0 1 1 0 1 1 0 1 1 0 1

여러분이 만들 수 있는 1이 연속된 연속부분수열은

이며 그 길이는 8입니다.

입력

첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000)이 주어집니다.

두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.

출력

첫 줄에 최대 길이를 출력하세요.

예시 입력 1 

14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1

예시 출력 1

8

 

 

 

<<풀이>>

 

-나의 풀이-

 

시간 복잡도 : O(N)

 

알고리즘 : 투 포인터

 

우선, ㅋㅋ 틀렸다. 예시 입력과 출력은 정답이지만 돌려보니 어디선가 오류가 있는 것 같다.

내 논리상 맞는거 같은데,, 어디서 문제일까 ㅠㅠ

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));
    }
}

 

-강사님 풀이-

 

시간 복잡도 : O(N)

 

알고리즘 : 투 포인터

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr) {
        int lt = 0,  cnt = 0, answer = 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));
    }
}

 

ㅋㅋㅋ 캬  ~ 멋지게 푸셨다. ㅋㅋ 아니 rt - lt + 1을 할 생각을 하다니..

 

일단은 나의 윗 문제가 왜 틀렸는지는 모르겠지만 확실히 강사님 방법은 직관적인 것은 분명하다. ㅠㅠ

 

그리고 내장 클래스 Math를 많이 쓰는데 코드 줄 줄이기에 정말 좋은거 같다!!

 

나도 활용 자주해야쓰겄다~~

 

*나의 풀이가 왜 틀렸는지 꼭 찾아와서 업뎃하겠다.