[TIL-17 / 230710] 알고리즘 - 슬라이딩 윈도우(백준 12891)

4. 슬라이딩 윈도우

• 슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다. 투 포인터 알고리즘과 매우 비슷하다.

---

[❌][백준 12891] DNA 비밀번호

12891번: DNA 비밀번호

백준(baekjoon) 12891 DNA 비밀번호

1단계 - 문제 분석하기

• P와 S의 길이가 1,000,000으로 매우 큼 → O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 함.
• 부분 문자열의 길이가 P → 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결 가능

슬라이딩 윈도우(sliding window)

• 길이가 P인 윈도우를 지정하여 배열 S의 시작점에 놓는다.
• 윈도우를 오른쪽으로 밀면서 윈도우에 잡힌 값들이 조건에 맞는지 탐색
• 배열 S의 길이만큼만 탐색을 진행하면 되므로 O(n)의 시간 복잡도로 문제 해결 가능

2단계 - 손으로 풀어 보기

• S 배열과 비밀번호 체크 배열을 저장

S배열과 비밀번호 체크 배열

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

유효한 비밀번호 판단 방법

• 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트
• 비밀번호 체크 배열과 비교하여 비밀번호 유효성 판단
• 현재 상태 배열을 업데이트할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트하는 방식으로 진행

문자열 업데이트 로직

• 위 그림의 경우 한 칸 이동하여 C가 빠지고, G가 추가되어 현재 상태 배열을 1, 2, 2, 3에서 1, 1, 3, 3으로 업데이트
• 고민해야할 사항
  • 실제 문자열과 관련된 배열 처리를 어떻게 할 것인지
  • 비밀번호 유효성 검사를 보다 바르게 할 수 있는 방법이 있는지

3단계 - 슈도코드 작성하기

// 데이터 저장
S(문자열 크기) P(부분 문자열 크기)
checkArr(비밀번호 체크 배열)
// 변수 선언
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P 범위(0 ~ P - 1)만큼 S 배열에 적용하고, 유효한 비밀번호인지 판단
for(i를 P에서 S까지 반복)
{
    j 선언(i - P)
    // 이 부분은 함수로 별도 구현
    한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리
    유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값에 업데이트
}
결괏값 출력

별도 함수
Add(문자 더하기 함수)
{
    새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경
}
Remove(문자 빼기 함수)
{
    제거되는 문자를 myArr에 업데이트하거나 checkSecret 값 변경
}

• 핵심은 유효한 비밀번호 검사 시에 기존 검사 결과에 새로 들어온 문자열, 제거되는 문자열만 반영하여 확인하는 것

4단계 - 코드 구현하기

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

public class Main {
    static int myArr[];
    static int checkArr[];
    static int checkSecret;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken()); // 임의로 만든 DNA 문자열 길이
        int p = Integer.parseInt(st.nextToken()); // 비밀번호로 사용할 부분 문자열 길이
        int result = 0;
        checkArr = new int[4]; // A,C,G,T의 최소 개수
        myArr = new int[4]; // 현재 부분 문자열 내의 A, C, G, T의 최소 개수
        char A[] = new char[s];
        checkSecret = 0; // 만족한 조건의 수

        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++;
            }
        }

        for (int i = 0 ; i < p ; i++) { // 부분 문자열 처음 받을 때 세팅
            Add(A[i]);
        }

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

        // 슬라이딩 윈도우
        for (int right = p ; right < s ; right++) {
            int left = right - p;
            Add(A[right]);
            Remove(A[left]);
            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--;
                myArr[0]--;
                break;
// >=가 안되는 이유: 만족하는 순간에 딱 한번만 checkSecret을 더함
// >=을 쓰면 계속 더해지기 때문에 안됨.
            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++;
                break;
// >=가 안되는 이유: 만족하는 순간에 딱 한번만 checkSecret을 더함
// >=을 쓰면 계속 더해지기 때문에 안됨.
            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;
        }
    }
}