#10 자바(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이 연속된 연속부분수열은

1 1 0 0  | 1 1 1 1 1 1 1 1 | 0 1

이고 그 길이는 8 을 만족하는 프로그램 작성

 

import java.util.Scanner;

public class Inflearn30 {
    public int solution(int N,int K, int[] A) {
        int answer = 0;                 // 출력 변수
        int count =0;                   // 0 을 1 로 바꾼 횟수
        int lt =0;
        for(int rt=0; rt<N; rt++) {
            if(A[rt] == 0) {
                count ++;
            }
            while(count>K) {
                if(A[lt] == 0) {
                    count --;
                }
                lt ++;
            }
            answer = Math.max(answer, rt - lt +1);
        }       // for문 //
        return answer;
    }

    public static void main(String[] args) {
        Inflearn30 inflearn30 = new Inflearn30();
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();          // 0,1 로 구성된 수열의 길이
        int K = scanner.nextInt();          // 0->1 이 가능한 최대 숫자
        int[] A = new int[N];
        for(int i=0; i<N; i++){
            A[i] = scanner.nextInt();
        }
        System.out.println(inflearn30.solution(N,K,A));
    }
}

< 풀이 > 

( c = count )

배열의 인덱스에 lt,rt를 두고 rt를 증가시킨다. 

rt == 0 이면 count 를 증가시킨다. 

만약 count 가 K 값 보다 커지는 경우에는 , lt == 0 일때까지 lt 를 증가시킨 후

count 값을 줄이고 lt의 인덱스를 증가시킨다. 

그리고 이 과정에서 길이의 최대값을 계속해서 갱신하여 준다. 

 

c = 0

길이 : rt - lt + 1 = 1

(1)

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

lt

rt

 

c = 0

길이 : rt - lt + 1 = 2

(2)

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

lt   rt

 

c = 1

길이 : rt - lt + 1 = 3

(3)

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

lt         rt

 

c = 2

길이 : rt - lt + 1 = 4

(4)

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

lt                rt           

 

c = 2

길이 : rt - lt + 1 = 5

(5)

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

lt                      rt

 

c = 2

길이 : rt - lt + 1 = 6

(6)

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

lt                             rt

 

c = 3

( count > k 에 걸림 ) -> ( lt==0 까지 lt 증가한 후 1을 0으로 바꾸어주고 lt 인덱스 증가 )

(7)

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

lt                                   rt

그리고 c = 2 로 변경

 

c = 2

길이 : rt - lt + 1 = 4

(8)

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

            lt ->lt              rt

 

c = 2

길이 : rt - lt + 1 = 7-3+1 = 5

(9)

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

                   lt                     rt

 

c = 2

길이 : rt - lt + 1 = 7-3+1 = 6

(10)

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

                   lt                           rt

 

c = 3

( count > k 에 걸림 ) -> ( lt==0 까지 lt 증가한 후 1을 0으로 바꾸어주고 lt 인덱스 증가 )

(11)

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

                  lt                                   rt

그리고 c = 2 로 변경

 

c = 2

길이 : rt - lt + 1 = 6

(12)

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

                  lt ->lt                          rt

 

c = 2

길이 : rt - lt + 1 = 7

(13)

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

                   lt                                         rt

 

c = 2

길이 : rt - lt + 1 = 8

(14)

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

                   lt                                              rt

 

c = 3

( count > k 에 걸림 ) -> ( lt==0 까지 lt 증가한 후 1을 0으로 바꾸어주고 lt 인덱스 증가 )

(15)

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

                   lt                                                     rt

 

c = 2

길이 : rt - lt + 1 = 6 (  (14)의 길이 8보다 작으므로 최대값 만족 x )

(16)

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

                   lt        ->         lt                             rt

 

 

 

 

 

 

출처 : https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의