백준 12891. DNA 비밀번호

문제 백준 12891. DNA 비밀번호

문제

문자열에 등장하는 모든 문자가 {A, C, G, T}로 이루어진 문자열을 DNA 문자열이라고 부른다.
{A, C, G, T}가 몇번 등장해야하는지 조건이 주어졌을때, 주어진 문자열로 DNA 문자열 비밀번호를 만들 수 있는 경우의 수를 구하여라.

입력

첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이 |P| 가 주어진다. (1 ≤ |P| ≤ |S| ≤ 1,000,000)

두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.

세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장된다.

출력

첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

풀이

문자열 AAACCTGCCAA가 주어졌을때 부분문자열의 길이가 4인 비밀번호를 만드는 경우의 수를 구하기 위해서는 주어진 문자열의 첫번째 문자부터 부분문자열의 길이만큼 잘라서 유효성 검사를 해야한다.

- 잘못된 풀이

나는 요즘은 시간복잡도를 계산하게 돼서 tle가 날 것 같으면 tle날 코드는 짜려는 시도조차 안한다. 딱 내가 이 문제를 접하고 tle를 낼 거 같은 코드가 먼저 생각이 났다.

for (int i = 0; i < 주어진 문자열 - 비밀번호 길이; i++)
	for (int j = 0; j < 비밀번호 길이; j++)
    	if (주어진 문자가 조건 만족하는지 판단)

tle를 생각하지 않는다면 중첩 for문으로 쉽게 구할 수 있을 것이다.
하지만 문제의 입력 범위를 살펴보자
문자열 S의 길이 1,000,0000, 부분 문자열 P의 길이 1,000,000 이다.
주어진 문자열 S의 길이가 100만이고, P가 10만인 경우라고 가정하면, i는 90만까지 반복하고, j는 10만번 반복하게 된다.
900,000 X 100,000 = 90,000,000,000 대략 90억번을 반복하게 된다.
1억번의 연산시간을 대략 1초라고 간주하기 때문에 tle가 날 것이다.

옳은 풀이

그렇다면 위 문제가 tle가 나지 않게 풀이하려면 어떻게 해야할까?
슬라이딩 윈도우방식을 적용한 풀이로 접근하도록 한다.

전체 길이 S에서 비밀번호 길이 P만큼을 초기값으로 두고 유효성을 검사한다. 이때 유효성 검사를 위한 배열 myArr[]을 두자.

현재 myArr[]에는 S에서 p만큼의 길이의 문자열에 대한 조건 충족여부에 대한 값들이 존재한다.
이제 반복문을 통하여 p 이후의 값들을 하나씩 집어넣어서 해당 문자가 조건을 충족하는지 여부를 판단하면서 경우의 수를 구해나간다.
당연히 p이후의 값들이 하나씩 추가되기 때문에 0, 1, 2, 3,,,, 차례대로 값들은 지워나가면서 경우의 수를 구해나가야한다.

풀이코드 java

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

public class boj12891 {

    static int acgt[];
    static int myArr[];
    static int checkCnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(stk.nextToken());
        int p = Integer.parseInt(stk.nextToken());

        char[] input = br.readLine().toCharArray();
        acgt = new int[4];
        myArr = new int[4];


        checkCnt = 0;
        int result = 0;
        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            acgt[i] = Integer.parseInt(stk.nextToken());
            if (acgt[i] == 0) {
                checkCnt += 1;
            }
        }

        for (int i = 0; i < p; i++) {
            add(input[i]);
        }

        if (checkCnt == 4)
            result++;


        for (int i = p; i < s; i++) {
            delete(input[i - p]); //맨앞에 있는 값을 지워줘야함
            add(input[i]);

            if (checkCnt == 4) {
                result++;
            }
        }

        System.out.println(result);

    }

    public static void add(char c) {
        switch (c) {
            case 'A':
                myArr[0] += 1;
                if (myArr[0] == acgt[0])
                    checkCnt += 1;
                break;
            case 'C':
                myArr[1]++;
                if (myArr[1] == acgt[1])
                    checkCnt++;
                break;
            case 'G':
                myArr[2]++;
                if (myArr[2] == acgt[2])
                    checkCnt++;
                break;
            case 'T':
                myArr[3]++;
                if (myArr[3] == acgt[3])
                    checkCnt++;
                break;
        }
    }

    public static void delete(char c) {
        switch (c) {
            case 'A':
                if (myArr[0] == acgt[0])
                    checkCnt -= 1;
                myArr[0] -= 1;

                break;
            case 'C':
                if (myArr[1] == acgt[1])
                    checkCnt--;
                myArr[1]--;

                break;
            case 'G':
                if (myArr[2] == acgt[2])
                    checkCnt--;
                myArr[2]--;

                break;
            case 'T':
                if (myArr[3] == acgt[3])
                    checkCnt--;
                myArr[3]--;

        }
    }

}