슬라이딩 윈도우 알고리즘

2개의 포인터로 범위를 지정한 다음, 범위(window)를 유지한 채로 이동(sliding)하여 문제를 해결

백준 - 12891번

1. 문제 분석

• P와 S의 길이가 1,000,000 으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제 해결해야함

2. 손으로 풀어보기

1️⃣ S배열과 비밀번호 체크 배열을 저장

2️⃣ 윈도우에 포함된 문자로 현재 상태 배열을 만듦. 다음 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단

3️⃣ 윈도우를 한 칸씩 이동하며 현재 상태 배열 업데이트

** 현재 상태 배열을 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트 하는 방식임

⇒ 빠지는 문자열 1개, 신규 문자열 1개씩만 비교하면 되므로 시간복잡도 낮음

3. 슈도코드 작성

// 데이터 저장
S(임의의 문자열 길이), P(부분 문자열 길이 == 윈도우 크기), A(문자열 데이터), checkArr(비밀번호 체크 배열)

// 변수 선언
myArr(현재상태배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P범위만큼 S배열에 적용하고, 유효한 비밀번호 인지 판단 (for문)
현재상태배열 업데이트는 메서드로 따로 구현

import java.io.*;
import java.util.*;

public class Main {
    static int[] myArr = new int[4];
    static int[] checkArr = new int[4];
    static int checkSecret = 0; // 4개 문자 중에 몇개가 충족하는지 (4가 되면 정답++)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());
        int result = 0;

        char[] arr = new char[S];

        arr = br.readLine().toCharArray();
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if(checkArr[i] == 0) {
                checkArr[i]++; // checkArr의 값이 0 이면 해당 문자는 없어도 된다는 뜻.
            }
        }

        // 처음 P 범위만큼 돌아서 현재 상태 배열 초기화
        for(int i = 0; i < P; i++) {
            add(arr[i]);
        }

        if(checkSecret == 4) result++;

        // 슬라이딩 윈도우
        // i = P 이 되는 순간, 윈도우는 다음으로 이동한다
        // 예) 이전 윈도우: [0, 1, 2, 3, ... P-1]
	      //     다음 윈도우: [1, 2, 3, ... P] -> 즉 빠질 문자 0, 들어올 문자 P
        for(int i = P; i < S; i++) {
            int j = i - P; // j: 빠질 문자 (== 이전 윈도우의 첫 문자)
            add(arr[i]);
            remove(arr[j]);
            if(checkSecret == 4) result++; // 한 번 이동할 때마다 확인
        }

        System.out.println(result);
        br.close();
    }

    private static void add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if(myArr[0] == checkArr[0]) checkSecret++;
                break;
            case 'C':
                myArr[1]++;
                if(myArr[1] == checkArr[1]) checkSecret++;
                break;
            case 'G':
                myArr[2]++;
                if(myArr[2] == checkArr[2]) checkSecret++;
                break;
            case 'T':
                myArr[3]++;
                if(myArr[3] == checkArr[3]) checkSecret++;
                break;
        }
    }

    private static void remove(char c) {
        switch (c) {
            case 'A':
                if(myArr[0] == checkArr[0]) checkSecret--;
                myArr[0]--;
                break;
            case 'C':
                if(myArr[1] == checkArr[1]) checkSecret--;
                myArr[1]--;
                break;
            case 'G':
                if(myArr[2] == checkArr[2]) checkSecret--;
                myArr[2]--;
                break;
            case 'T':
                if(myArr[3] == checkArr[3]) checkSecret--;
                myArr[3]--;
                break;
        }
    }
}