[JAVA] 백준 12891 슬라이딩 윈도

 

12891번: DNA 비밀번호

문제

주어진 문자열의 부분문자열이 주어진 요구사항을 만족하는 경우의 수를 출력

풀이

다음과 같은 규칙으로 해결하였다.

먼저 요구하는 조합을 배열에 넣고 이때 0이라면 check++해주었다.

초기화하는 로직으로 end값을 M까지 높이면서 arr[end]의 값에 따라 pass의 값을 추가해주었다.

값을 추가했을 때 만약 요구하는 조합과 같다면 check++했다.

이제 end를 1칸씩 늘리고 start도 한 칸씩 늘리면서 pass를 갱신해갔다.

start를 높이면 값을 1개빼는 것이기 때문에 해당 값을 pass에서 빼고 만약 이전에 check되어있던 값이라면 check값도 1 낮췄다.

end를 높이면 값을 1개 추가하는 것이기 때문에 해당 값을 pass에서 추가하고 만약 요구하는 값과 같다면 check++를 해주었다.

이렇게 모든 부분 문자열 end가 N보다 작을 때 까지 검사한 후 값을 출력한다.

슬라이딩 윈도를 한칸씩 이동하면서 start와 end를 추가하고 빼는 연산을 진행하였다.

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] req = new int[4];
        int[] pass = new int[4];

        int start = 0;
        int end = 0;
        int check = 0;
        int answer = 0;
        char[] arr = br.readLine().toCharArray();
        st = new StringTokenizer(br.readLine(), " ");


        for(int i=0; i<4; i++){
            req[i] = Integer.parseInt(st.nextToken());
            if(req[i] == 0 ) check++;
        }


        while(end < M){
            int target = check(arr[end++]);
            if(++pass[target] == req[target]) check++;
        }

        if(check == 4) answer++;

        while(end < N){
            int minus = check(arr[start++]);
            int plus = check(arr[end++]);

            if(pass[minus]-- == req[minus]) check--;

            if(++pass[plus] == req[plus]) check++;

            if(check == 4) answer++;
        }
        System.out.println(answer);


    }
    private static int check(char x){
        switch(x){
            case 'A':
                return 0;
            case 'C':
                return 1;
            case 'G':
                return 2;
            case 'T':
                return 3;
        }
        return 0;
    }

}

결과