[Java] 백준 12891번 문제(DNA 비밀번호)

원본 링크 : https://www.acmicpc.net/problem/12891

 

문제설명

 

 

소스코드

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

public class Boj_12891
{
    static int[] inputACGT = new int[4]; // 입력 받은 부분문자열에 포함되어야 할 최소 개수
    static int[] countACGT = 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 count = 0; // 정답을 저장하는 변수

        // n과 m을 받아옴
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 문자열을 받아옴
        char[] str = br.readLine().toCharArray();

        // 입력 받은 부분문자열에 포함되어야 할 최소 개수를 받아옴
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < inputACGT.length; i++) inputACGT[i] = Integer.parseInt(st.nextToken());

        // 초기 윈도우 구성
        for (int i = 0; i < m; ++i) add(str[i]);
        if (check()) ++count;

        // 슬라이딩 윈도우
        for (int startPtr = 0; startPtr < n - m; ++startPtr)
        {
            int endPtr = startPtr + m;
            remove(str[startPtr]); // str의 앞 문자열을 제거
            add(str[endPtr]); // str의 뒷 문자열을 추가
            if (check()) ++count;
        }

        System.out.println(count);
    }

    static void add(char c)
    {
        if (c == 'A') ++countACGT[0];
        else if (c == 'C') ++countACGT[1];
        else if (c == 'G') ++countACGT[2];
        else ++countACGT[3];
    }

    static void remove(char c)
    {
        if (c == 'A') --countACGT[0];
        else if (c == 'C') --countACGT[1];
        else if (c == 'G') --countACGT[2];
        else --countACGT[3];
    }

    static boolean check()
    {
        for (int i = 0; i < 4; ++i) if (countACGT[i] < inputACGT[i]) return false;
        return true;
    }
}

 

설명

이 예시로 그림으로 표현하면

inputACGT는 입력 받은 부분문자열에 포함되어야할 최소 개수이다.

 

초기 윈도우 구성을 마치면 countACGT는 현재까지 윈도우에서 각 알파벳의 출현 숫자를 기록한 배열이고, 아래와 같다.

잊지말아야할 것은 초기 윈도우를 구성하고 check 메서드를 통해서 현재까지 부분 문자열은 문제없는지 검사해야한다.

static boolean check()
{
    for (int i = 0; i < 4; ++i) if (countACGT[i] < inputACGT[i]) return false;
    return true;
}

 

 

슬라이딩 윈도우 for문을 살펴보면 아래와 같다.

여기서 startPtr의 값을 빼주고(remove) endPtr의 값을 추가(add)해준다.

static void add(char c)
{
    if (c == 'A') ++countACGT[0];
    else if (c == 'C') ++countACGT[1];
    else if (c == 'G') ++countACGT[2];
    else ++countACGT[3];
}

static void remove(char c)
{
    if (c == 'A') --countACGT[0];
    else if (c == 'C') --countACGT[1];
    else if (c == 'G') --countACGT[2];
    else --countACGT[3];
}

add()와 remove()를 수행했다면 countACGT 배열은 아래와 같이 된다.

이 때 check() 메서드가 true를 리턴하므로 count가 +1 된다.

 

 

다음 슬라이딩 윈도우를 하면 아래와 같이 된다.

이 때 check() 메서드가 true를 리턴하므로 count가 +1 된다.

총 2번 check() 메서드가 true를 리턴했으므로 정답은 2가된다.