최대 길이 연속 부분 수열

22 Apr 2023 in Algorithm on Java, Coding, Test

문제

설명

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

해결방법

• two pointer 사용 문제.

• 부분 수열의 길이를 어떻게 체크할 것인가?

  무조건 0을 1로 바꾸고 체크하는 것이 포인트.

  최대 횟수를 맞추기 위해 원래 무슨 값이 었는지 체크 해야 하므로 원래 배열은 건드리지 않고 체크 한다.

  

코드

import java.util.*;

class Main {
    public int solution(int n, int k, int[] arr) {
        int answer = 0, cnt = 0, lt = 0;
        // 포인터 2개를 사용하여 하나는 순회용도로 사용하고
        // 하나는 합을 넘겼을 시, 뺄 때 사용하는 용도로 사용한다.
        for (int rt = 0; rt < n; rt++) {
            // 만약, 해당 자리 수가 0이라면 1로 바꾼다고 생각하고 횟수를 1증가
            if (arr[rt] == 0) cnt++;
            // 만약 횟수가 최대 횟수를 넘겼다면, 다른 포인터를 이용해
            // 원래 0 이었던 자리를 다시 0으로 바꾼다고 생각하고 횟수를 1 뺀다.
            while (cnt > k) {
                if (arr[lt] == 0) cnt--;
                lt++;
            }
            // 최대 횟수까지 바꿨을 때, 현재 포인터의 위치를 이용해 길이를 구하여 
            // 최대인 경우를 구한다.
            answer = Math.max(answer, rt - lt + 1);
        }
        return answer;
    }

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