[백준] 12891_DNA 비밀번호 - JAVA

백준_12891

12891번: DNA 비밀번호

 

 

슬라이딩 윈도우

슬라이딩 윈도우 알고리즘은 두 개의 포인터로 범위를 지정한 다음, 그 범위를 유지한 채로 이동하며 문제를 해결한다.

예를들면, 슬라이딩 윈도우의 배열이 3인 슬라이딩 윈도우의 첫 번째 for문 범위는 아래와 같다.

그 다음 반복일 때는 슬라이딩 윈도우가 옆으로 이동하여 아래 그림과 같이 범위가 지정된다.

슬라이딩 윈도우의 범위만큼만 탐색을 진행하기 때문에 O(n)의 시간 복잡도로 문제를 해결할 수 있다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {

    static int checkArr[];
    static int myArr[];
    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());

        // S : DNS 문자열 길이, P : 부분 문자열 길이
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        int result = 0;
        char A[] = new char[S];
        checkArr = new int[4];
        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++) { // 초기 P 부분 문자열 처리 부분
            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++; // 4자릿수와 관련된 크기가 모두 충족될 때 유효한 비밀번호
        }

        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' :
                if(myArr[0] == checkArr[0]) checkSecret--;
                myArr[0]--;
                break;
            case 'C' :
                if(myArr[1] == checkArr[1]) checkSecret--;
                myArr[1]--;
                break;
            case 'G' :
                if(myArr[2] == checkArr[2]) checkSecret--;
                myArr[2]--;
                break;
            case 'T' :
                if(myArr[3] == checkArr[3]) checkSecret--;
                myArr[3]--;
                break;
        }
    }
}

 

 

제출 결과