[슬라이딩 윈도우 실전문제] DNA 비밀번호 - 백준12891

 

슬라이딩 윈도우는 O(n)의 시간 복잡도를 가져 쉽게 문제를 풀 수 있다.

 

s배열(기본 배열)과 비밀 번호 체크 배열을 설정한다.

윈도우에 포함된 문자로 현재 상태 배열을 만들고 현재 상태 배열과 비밀 번호 체크 배열을 비교한다.

비교 후 답이 되지 않는다면 한 칸 이동해 다시 비교한다. 이때, 빠진 첫 번째 인덱스 값과 들어온 새 인덱스 값만 비교하여 정보를 업데이트 해준다.

 

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

public class 슬라이딩_비밀번호 {
    static int myArr[];
    static int checkArr[];
    static int checkSecret;

    public static void main(String[] args) throws IOException {
        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());
        int result = 0;
        checkArr = new int[4]; //체크 배열
        char A[] = new char[S]; //기본 배열
        myArr= new int[4];//현재 상태 배열
        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 i = P; i<S; i++) {
            int j = i-P;
            Add(A[i]);
            remove(A[j]);

            if(checkSecret == 4) {
                result++;
            }
        }
        System.out.println(result);
        br.close();
    }

    private static void Add(char c) {
        switch (c) {
            case 'A':
                myArr[0]++;
                if(myArr[0] == checkArr[0]) checkSecret++;
                break;
            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;
        }
    }

    private static void remove(char c) {
        switch (c) {
            case 'A':
                myArr[0]--;
                if(myArr[0] == checkArr[0]) checkSecret--;
                break;
            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;
        }
    }
}