슬라이딩 윈도우

2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결

https://www.acmicpc.net/problem/12891

1. 문제 분석하기

P와 S의 길이 : 1000000

→ O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 함.

이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결할 수 있다.

범위(window)를 먼저 잡음.

슬라이딩 윈도우에서는 이 범위가 유지됨.

조건에 맞는지 파악한 후 맞으면 cnt++

크기 유지한 채로 다음으로 이동

2) 손으로 풀어 보기

1. S 배열과 비밀번호 체크 배열을 저장한다.

   

2. 윈도우에 포함된 문자로 현재 상태 배열(이 문자열에서 ACGT가 몇개 있는가)을 만든다.(핵심) 그 후 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단한다.

   

3. 윈도우를 한 칸씩 이동하여 현재 상태 배열을 업데이트한다.

   현재 상태 배열을 업데이트한 이후에는 비밀번호 체크 배열과 비교하여 비밀번호 유효성을 판단한다.

   현재 상태 배열을 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행한다.

   

   한 칸씩만 이동.

   이동할 때 앞쪽에 하나가 빠지고, 뒤쪽에 하나가 추가로 들어옴!

   

   가운데에 있는 애들은 더이상 볼 필요 없음.

   빠져나간 것만큼 빼주고 새로운 들어온 만큼 하나 더해주면 되므로 2개의 데이터만 넣고 빼면 된다!

   이 상태에서 비밀번호 체크 배열과 비교한다.

+) 이 문제는 슬라이딩 윈도우 원리 이외에도

‘실제 문자열과 관련된 배열 처리를 어떻게 할 것인가?’,

‘비밀번호 유효성 검사를 보다 빠르게 할 수 있는 방법이 있을까?’ 등

코드 레벨에서 고민이 필요한 부분이 있다.

3) 슈도코드 작성하기

// 데이터 저장
S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkArr(비밀번호 체크 배열)

// 변수 선언
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P 범위(0 ~ P - 1)만큼 S 배열에 적용하고, 유효한 비밀번호인지 판단하기
for (i를 P에서 S까지 반복)
{
	j 선언(i - P)
	// 이 부분은 함수로 별도 구현하기
}

4) 실제 코드 작성하기

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

public class Main {
    static int[] myArr;
    static int[] checkArr;
    static int checkSecret;
    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;
        checkArr = new int[4]; // 비밀번호 체크 배열
        myArr = new int[4]; // 현재 상태 배열
        char[] a = new char[s];
        checkSecret = 0; // 현재 p개 중 몇개가 비밀번호 요건에 만족하는지

        a = 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) {
                checkSecret++; // i번째 값은 이미 완성됨.
            }
        }

        for (int i = 0; i < p; i++) { // 부분 문자열 처음 받을 때 세팅
            Add(a[i]);  // 현재 상태 배열에 담음
        }

        if (checkSecret == 4) {
            result++;
        }

        // 슬라이딩 윈도우
        for (int i = p; i < s; i++) {
            int j = i - p; // j = 맨 왼쪽, i = 맨 오른쪽
            Add(a[i]); // 오른쪽에 있는 값 추가
            Remove(a[j]);
            if (checkSecret == 4) {
                result++;
            }
        }

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

    private static void Remove(char c) {
        switch (c) {
            case 'A':
                if (myArr[0] == checkArr[0]) // 같으면 이번에 빠짐으로써 충족이 안 되는 것이니까 checkSecret 하나 줄임
                    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;
        }
    }

    private static void Add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if (myArr[0] == checkArr[0])
                    checkSecret++; // 'A'가 더 많이 들어온다고 해서 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;
        }
    }


}