[투포인터] 최대 길이 연속부분수열 .java

설명

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

 

 

 내 풀이

 

1. rt가 가리키는 값이 0이면 0의 개수를 의미하는 zeroCount를 하나 증가

2. zeroCount가 k라면 현재의 길이(rt - lt + 1)을 최댓값으로 갱신

3. 만약 zeroCount가 k보다 크면 0의 개수를 줄이기 위해 lt의 값이 0이면 0의 개수를 줄임 => lt++

 

zeroCount가 k보다 커지는 그 직전 인덱스까지가 최댓값임을 이용하려고 했지만

더 복잡해지는 것 같아 zeroCount가 k일 때의 모든 길이를 현재의 최댓값과 비교하여 계속 갱신하도록 구현했다

 

import java.util.Scanner;

public class Main {

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

        int answer = 0;
        int lt = 0;
        int zeroCount = 0;
        
        for(int rt = 0; rt < n; rt++) {

            if(arr[rt] == 0) {//값이 0이면 0개수 증가
                zeroCount++;
            }

            while(zeroCount > k) {
                if(arr[lt] ==0) zeroCount--;//lt가 0이면 0개수 하나 감소
                lt++;//0개수가 감소하든 아니든 lt는 증가

            }
            if(zeroCount == k ) {//최댓값으로 갱신
                answer = Math.max(answer, rt-lt+1);}

        }

        System.out.println(answer);
    }
}

 

 

 

다른 풀이

내가 k가 2일 때만 길이를 갱신한 반면, k와 관계없이 계속 갱신하는 점만 다른 코드이다

 

import java.util.Scanner;

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

        int cnt = 0;//현재 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;
    }
    public static void main(String[] args) {
        Main T = new Main();
        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.print(T.solution(n, k, arr));
    }
}

 

 

 

 

 

💡💡

answer값을 갱신하는 순서가 고민이라 여러 번 실행했다

어차피 0의 개수가 k보다 크면 결국 k가 될 때까지 while문을 실행하기 때문에 이 while문 뒤에 배치하면 되었다

순서대로 생각하자~!!!