[인프런 알고리즘] Chpater 3, 6번 문제(최대 길이 연속부분 수열)

이 알고리즘 문제는 인프런의 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 (김태원)의 문제입니다.

---

문제 설명

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class sec03_06 {
    public static int solution(int[] arr, int N, int K) {
        int maxLength = 0;
        int lPtr = 0, count = 0;
        for(int rPtr = 0; rPtr < N; ++rPtr)
        {
            if(arr[rPtr] == 0) ++count;
            while(count > K) if(arr[lPtr++] == 0) --count;
            if(rPtr - lPtr + 1 > maxLength) maxLength = rPtr - lPtr + 1;
        }


        return maxLength;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        System.out.println(solution(arr, N, K));
    }
}

 

설명

• 투 포인터와 슬라이딩 윈도우 알고리즘 사용
  -lPtr과 rPtr 두 개의 포인터를 사용하여 현재 윈도우를 관리한다.
  -count는 현재 윈도우 내에 있는 0의 개수를 저장한다.
  -rPtr을 증가시키면서 윈도우를 오른쪽으로 확장한다.
  -윈도우 내의 0의 개수가  K 를 초과하면 lPtr을 증가시켜 윈도우를 축소한다.
  -윈도우의 길이가 최대 길이를 갱신할 때마다 maxLength를 업데이트한다.
• 슬라이딩 윈도우 확장
  -배열의 시작부터 끝까지 반복 (rPtr 오른쪽 포인터를 0부터 N-1까지 이동).
  -현재 요소(arr[rPtr])가 0이면, count를 증가시킨다.
• 윈도우 축소
  -만약 count가  K 보다 커지면, 즉 윈도우 내의 0의 개수가  K 를 초과하면:
  -윈도우의 왼쪽 끝(lPtr)을 오른쪽으로 이동하여 윈도우를 축소한다.
  -만약 lPtr이 가리키는 요소가 0이면, count를 감소시킨다.
• 최대 길이 갱신
  -현재 윈도우의 길이(rPtr - lPtr + 1)가 maxLength보다 크면, maxLength를 갱신한다.