[백준 12891] DNA 비밀번호 (Java) - 슬라이딩 윈도우

codingNoob12·2026년 3월 4일

슬라이딩 윈도우

알고리즘

목록 보기

84/107

🚀 문제 핵심

임의의 DNA 문자열(A, C, G, T)에서 부분 문자열을 뽑았을 때, 등장하는 각 문자의 개수가 특정 기준 이상인 경우의 수를 구하는 문제입니다.

문자열 길이(S): 최대 1,000,000
부분 문자열 길이(P): 최대 1,000,000
특이사항: 슬라이딩 윈도우를 사용하지 않고 매번 부분 문자열을 새로 검사하면 $O(S \times P)$ 로 시간 초과가 발생합니다.

💡 해결 전략: 슬라이딩 윈도우 (Sliding Window)

윈도우의 크기가 $P$ 로 고정되어 있으므로, 한 칸씩 이동할 때마다 '새로 들어오는 문자'와 '나가는 문자'만 업데이트하면 $O(S)$ 의 시간 복잡도로 해결할 수 있습니다.

윈도우 확장: 오른쪽 포인터(j)를 이동하며 문자 카운트를 늘립니다.
윈도우 유지: 윈도우의 크기가 $P$ 가 되면 현재 상태가 조건을 만족하는지 체크합니다.
윈도우 축소: 왼쪽 포인터(i)를 이동하기 전, 윈도우에서 빠져나가는 문자의 카운트를 줄입니다.

💻 구현 코드 (Java)

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

public class Main {
    public static void main(String[] args) throws Exception {
        try (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());

            char[] dna = br.readLine().toCharArray();

            st = new StringTokenizer(br.readLine());
            int[] need = new int[4]; // A, C, G, T 최소 개수
            for (int i = 0; i < 4; i++) {
                need[i] = Integer.parseInt(st.nextToken());
            }

            int i = 0, j = 0, answer = 0;
            int[] count = new int[4]; // 현재 윈도우 내 문자 카운트

            while (j < s) {
                // 1. 새로운 문자 추가 (Window Expand)
                count[idx(dna[j++])]++;

                // 2. 윈도우 크기가 P에 도달했을 때
                if (j - i == p) {
                    if (isFullfill(count, need)) {
                        answer++;
                    }

                    // 3. 가장 오래된 문자 제거 (Window Shrink)
                    count[idx(dna[i++])]--;
                }
            }
            System.out.println(answer);
        }
    }

    // 조건 만족 여부 확인
    private static boolean isFullfill(int[] count, int[] need) {
        for (int k = 0; k < 4; k++) {
            if (count[k] < need[k]) return false;
        }
        return true;
    }

    // 문자별 인덱스 매핑
    private static int idx(char c) {
        switch (c) {
            case 'A': return 0;
            case 'C': return 1;
            case 'G': return 2;
            case 'T': return 3;
            default: return -1;
        }
    }
}