[인프런] 최대 길이 연속 부분 수열 (투 포인터^)

문제
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로 구성된 수열이 주어집니다.

 

출력
첫 줄에 최대 길이를 출력

 

예제 입력
14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1


예제 출력
8

 

 

 

 

문제 풀이

투 포인터를 이용한 연속 부분 수열을 찾는 문제입니다.

 

rt의 시점(K + 1개만큼 0을 바꾼 상황)에서 lt를 적절히 옮기고 그 갯수를 세는 것이 이 문제의 핵심 포인트입니다.

 

 

 

K(0을 바꿀 수 있는 횟수)보다 cnt가 작거나 같을 동안은 rt를 이동시킵니다.

 

만약 cnt가 더 크다면 lt를 옮기다가 0을 만났을 때 cnt를 1 감소시킵니다. 

 

중요한 것은 0을 만났을 때의 위치(예시에서 index 2)는 0으로 바꿔주기 때문에 실제 계산은 그 다음 위치(index 3)부터 이루어져야 합니다.

 

즉 위 그림에서 마지막 상황은 0으로 바뀐 index2의 다음 위치인 index 3과 index 6의 위치를 1로 바꿔서 3~6까지 총 4개를 세야합니다.

 

 

 

 

 

코드

public static int solution(int N, int[] arr, int K) {
    int answer = 0;

    int cnt = 0;
    int lt = 0;

    // rt 증가
    for (int rt = 0; rt < N; rt++) {
        if (arr[rt] == 0) {
            cnt++;
        }

        // K개보다 0을 바꾼 숫자가 적을 때까지
        while (cnt > K) {
            if (arr[lt] == 0) cnt--; // 현재 lt의 위치가 원래 0이라면 개수를 줄여줌
            lt++;
        }
        answer = Math.max(answer, rt - lt + 1); // 매번 길이가 최대인지를 검사
    }

    return answer;
}

 

 

 

 

발생한 문제

1) 코드를 효율적으로 짜는 것이 중요하다.

해답에서는 while -> if 순으로 작성하였는데, 처음 코드 작성 시 if -> while 순으로 작성해서 코드가 더 꼬였다.

 

 

 

2) 모든 문제에서 위치를 굳이 저장할 필요가 없다.

처음에는 next 변수를 두고 lt가 다음으로 변경되어야 할 위치를 저장하려고 했으나, 로직이 더 복잡해졌다.

 

단순하게 생각해서 구현하더라도 시간초과가 나지 않는다면 오히려 더 간결하고 효율적인 코드를 작성할 수 있다.