[투포인터] 12891. DNA비밀번호

[BOJ] 12891. DNA비밀번호

📝 나의 풀이

1년 전에 풀었던 문제인데
부분 집합으로 접근했다가 시간 초과가 떴고, 투포인터로 풀었다.

DNA 문자열에서 특정 부분 문자열이 주어진 조건을 만족하는지 확인하는 문제다.
주어진 부분 문자열의 길이 P와 DNA 문자열의 길이 S가 주어지며, A, C, G, T 각각의 최소 개수 조건이 주어진다. 슬라이딩 윈도우 기법을 사용하여 각 부분 문자열이 조건을 만족하는지 확인하고, 만족하는 경우의 수를 계산한다.

📌 풀이 과정

1. 초기 윈도우 설정

   • 처음 P개의 문자를 슬라이딩 윈도우에 포함시켜, 이 윈도우 내에서 A, C, G, T 각각의 개수를 curCount 배열에 저장한다.
   • 초기 윈도우가 조건을 만족하는지 isValid() 메서드를 통해 확인하고, 조건을 만족하면 answer를 1 증가시킨다.

2. 슬라이딩 윈도우 적용

   • 문자열을 순회하며 윈도우를 한 칸씩 오른쪽으로 이동시킨다.
   • 윈도우의 왼쪽 끝 문자를 제거하고, 오른쪽 끝에 새 문자를 추가하여 curCount 배열을 업데이트한다.
   • 업데이트된 윈도우가 조건을 만족하는지 isValid() 메서드를 통해 확인하고, 조건을 만족하면 answer를 1 증가시킨다.

👩🏻‍💻 제출 코드

package 투포인터;

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

public class DNA비밀번호_12891 {

    static int S, P, answer = 0;
    static String pw;
    static int[] DNA = new int[4]; // A, C, G, T
    static int[] curCount = new int[4]; // 현재 윈도우 내의 DNA 개수

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken()); // DNA 문자열 길이
        P = Integer.parseInt(st.nextToken()); // 부분문자열 길이
        pw = br.readLine(); // 임의로 만든 DNA 문자열

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            DNA[i] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i < P; i++) {
            int idx = mapCharToIndex(pw.charAt(i));
            curCount[idx]++;
        }

        if(isValid()) answer++;

        for(int i = P; i < S; i++) {
            int left = mapCharToIndex(pw.charAt(i - P));
            curCount[left]--;

            int right = mapCharToIndex(pw.charAt(i));
            curCount[right]++;

            if(isValid()) answer++;
        }


        System.out.println(answer);

    }


    private static int mapCharToIndex(char c) {
        switch (c) {
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
            default:
                return -1;
        }
    }

    private static boolean isValid(){
        for(int i = 0; i < 4; i++) {
            if(curCount[i] < DNA[i]) return false; // 하나라도 최소 조건을 만족하지 않으면
        }
        return true;
    }
}