section3.5

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이 연속된 연속부분수열은
1 1 0 0 ( 1 1 '1' 1 1 '1' 1 1 ) 0 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

 

 

 

ANSWER

package practice.section3;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Question6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] arr = new int[n];
        for (int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(solution(n, k, arr));
    }

    public static int solution(int n, int k, int[] arr) {
        int answer = 0;
        int lt = 0;
        int sum = 0;
        int zeroCnt = 0;
        int max = 0;

        for (int rt = 0; rt < arr.length; rt ++) {

            if (arr[rt] == 0) {
                zeroCnt++;
            }
            sum += arr[rt];

            while (zeroCnt != k) {
                sum += arr[lt++];
                if (arr[lt] == 0) {
                    zeroCnt ++;
                }

            }

            if (sum > max) {
                max = sum;
            }

            zeroCnt = 0;

        }

        sum = max;

        // map > (합, 0의 cnt) > 전체 돌면서 max값 구하기 : 시간이 너무 오래 걸릴 것 같음


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

        return sum;
    }

}

• 풀다가 시간이 너무 오래 걸릴 것 같아서 포기했다
• 생각으로는 map에 원래 했던 대로 합을 구하고 0의 cnt값을 넣어서 max 구하면 될 것 같은데 시간 초과될 것 같았다
• 0의 개수를 세서 잘 풀면 될 것 같은데 모르겠다  

 

 

 

SOLUTION

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

    public int solution(int n, int k, int[] arr) {
        int answer = 0;
        int cnt = 0;
        int lt = 0;

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

        return answer;
    }

}

• 1과 0 으로만 이루어져 있지만 합을 길이를 구하는 방식으로 대체한다고 생각을 못했다
• 아직 투포인터 알고리즘에 익숙하지 않아서 사용법을 잘 몰랐던 것 같다
• 이렇게 코드가 간단할 수가 ...