[🧠 Do it! 알고리즘] 2-4. 슬라이딩 윈도우(Sliding Window)

🧠 목차

1. 슬라이딩 윈도우(Sliding Window)
2. [실전 문제] DNA 비밀번호 (백준 12891)

---

1. 슬라이딩 윈도우(Sliding Window)

• 2개의 포인터로 범위를 지정한 후, 일정한 구간(window)을 유지하며 이동시키는 방식으로 데이터를 처리하는 알고리즘
• 보통 연속된 부분 배열(subarray)이나 부분 문자열(substring)의 합, 최대/최소값, 조건 만족 여부 등을 빠르게 구할 때 사용된다.
• 투 포인터 알고리즘과 매우 비슷하다.
• 시간복잡도 O(N)

---

2. [실전 문제] DNA 비밀번호 (백준 12891)

문제: DNA 비밀번호 https://www.acmicpc.net/problem/12891

 

import java.util.Arrays;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int answer = 0;

        int s = sc.nextInt();
        int p = sc.nextInt();
        sc.nextLine();
        
        String str = sc.nextLine();
        int[] rule = Arrays.stream(sc.nextLine().split(" "))
        		.mapToInt(Integer::parseInt).toArray();
		
        // 초기 세팅
        int[] count = new int[4];
        for (int i = 0; i < p; i++) {
            addChar(count, str.charAt(i));
        }

        if (isValid(count, rule)) answer++;

        for (int i = p; i < s; i++) {
            addChar(count, str.charAt(i));               // 들어온 문자
            removeChar(count, str.charAt(i - p));  	// 나간 문자

            if (isValid(count, rule)) answer++;
        }

        System.out.println(answer);
    }

    private static void addChar(int[] count, char c) {
        switch(c) {
            case 'A' -> count[0]++;
            case 'C' -> count[1]++;
            case 'G' -> count[2]++;
            case 'T' -> count[3]++;
            default -> {}
        }
    }

    private static void removeChar(int[] count, char c) {
        switch(c) {
            case 'A' -> count[0]--;
            case 'C' -> count[1]--;
            case 'G' -> count[2]--;
            case 'T' -> count[3]--;
            default -> {}
        }
    }

    private static boolean isValid(int[] count, int[] required) {
        for (int i = 0; i < 4; i++) {
            if (count[i] < required[i]) return false;
        }
        return true;
    }
}