백준 12891(DNA 비밀번호) JAVA <슬라이딩 윈도우>

문제

12891번: DNA 비밀번호

문자열 S가 주어지면 부분 문자열 P에서 최소 DNA문자{A, C, G, T} 의 각각의 개수를 만족하는 

부분문자열의 개수를 구하는 문제입니다.

예를 들어 S = AAACCTGCCAA 이고 P = 4, {A, C, G, T} = {1, 1, 1, 0}이라면

"GCCA" 가 조건을 만족한다.

 

문자열의 길이가 최대 1000000이므로 완전탐색을 하게 되면 시간초과가 납니다.

따라서 시작 인덱스와 끝 인덱스를 옮기는 "슬라이딩 윈도우" 방법을 사용했습니다.

 

아이디어는 P 길이의 부분 문자열을 돌아보면서 {A, C, G, T}의 개수를 세고, 최소 {A, C, G, T}를 만족하는지 확인합니다.

static int []myArr = new int[4]; //내가 설정한 P 부분문자열의 {A, C, G, T} 개수 세는 배열
static int []checkArr = new int[4]; //문제에서 요구한 {A, C, G, T}의 최소 개수 배열

char str[] = new char[S]; //전체 문자열 받는 공간
 str = br.readLine().toCharArray(); //전체 문자열

 st = new StringTokenizer(br.readLine()," ");

 for(int i=0;i<4;i++){
     checkArr[i] = Integer.parseInt(st.nextToken()); //문제에서 요구한 {A, C, G, T} 개수
 }

        for(int i= 0;i<P;i++){ //먼저 0번째 인덱스를 처음 으로 잡고 {A, C, G, T}의 개수를 센다
            if(str[i]=='A')myArr[0]++;
            if(str[i]=='C')myArr[1]++;
            if(str[i]=='G')myArr[2]++;
            if(str[i]=='T')myArr[3]++;
        }
        int ans = 0;
        if(checkCounting()) //현재 myArr에서 센 A, C, G, T의 checkArr 의 개수에 만족하는지
            ans++;

checkCounting()은 말 그대로 현재 내가 보고 있는 부분문자열 P가 A, C, G, T의 개수를 만족하는지 보는 것입니다.

만족하면 ans를 늘려주어 개수를 세어줍니다.

static boolean checkCounting(){
        for(int i = 0;i<4;i++){
            if(myArr[i]<checkArr[i])
                return false;
        }
        return true;
    }

이제 슬라이딩 윈도우를 해야 합니다.

        int i = -1;
        for(int j = P;j<S;j++){
            i = j - P; //이전 부분문자열의 시작을 나타내는 위치

            //이전 부분문자열의 시작 문자 제외
            if(str[i]=='A')myArr[0]--;
            if(str[i]=='C')myArr[1]--;
            if(str[i]=='G')myArr[2]--;
            if(str[i]=='T')myArr[3]--;

            //이전 부분문자열의 끝에서 1문자 추가
            if(str[j]=='A')myArr[0]++;
            if(str[j]=='C')myArr[1]++;
            if(str[j]=='G')myArr[2]++;
            if(str[j]=='T')myArr[3]++;

            if(checkCounting())ans++;
        }

i는 P문자열의 시작 인덱스를 나타냅니다.

아까 위에서 우리는 맨 처음 부분문자열을 봤으므로 일단 이전 부분문자열의 시작 부분을 빼줘야 합니다.

그 다음 j는 원래 P문자열을 한칸 오른쪽으로 옮긴 인덱스입니다.

i가 왼쪽 파란색 부분이고 j가 오른쪽 파란색 부분입니다.

옮길 때 마다 checkCounting()을 사용해 조건이 만족하는지 확인합니다.

---

전체 코드입니다.

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

public class boj12891 {
    static int []myArr = new int[4];
    static int []checkArr = new int[4];

    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());


        char str[] = new char[S];
        str = br.readLine().toCharArray(); //DNA 문자열

        st = new StringTokenizer(br.readLine()," ");

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

        for(int i= 0;i<P;i++){ //A, C, G, T의 개수를 센다
            if(str[i]=='A')myArr[0]++;
            if(str[i]=='C')myArr[1]++;
            if(str[i]=='G')myArr[2]++;
            if(str[i]=='T')myArr[3]++;
        }
        int ans = 0;
        if(checkCounting())
            ans++;

        int i = -1;
        for(int j = P;j<S;j++){
            i = j - P; //이전 부분문자열의 시작을 나타내는 위치

            //이전 부분문자열의 시작 문자 제외
            if(str[i]=='A')myArr[0]--;
            if(str[i]=='C')myArr[1]--;
            if(str[i]=='G')myArr[2]--;
            if(str[i]=='T')myArr[3]--;

            //이전 부분문자열의 끝에서 1문자 추가
            if(str[j]=='A')myArr[0]++;
            if(str[j]=='C')myArr[1]++;
            if(str[j]=='G')myArr[2]++;
            if(str[j]=='T')myArr[3]++;

            if(checkCounting())ans++;
        }
        System.out.println(ans);

    }
    static boolean checkCounting(){
        for(int i = 0;i<4;i++){
            if(myArr[i]<checkArr[i])
                return false;
        }
        return true;
    }
}