[백준 - 12891] DNA 비밀번호 .java

https://www.acmicpc.net/problem/12891

문제

평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.

 

하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다. 그래서 민호는 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이어야 비밀번호로 사용할 수 있다는 규칙을 만들었다.

 

임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하자. 그리고 부분문자열에 ‘A’는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이 등장해야 비밀번호로 사용할 수 있다고 하자. 이때 “ACCT” 는 ‘G’ 가 1 개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용하지 못한다. 하지만 “GCCA” 은 모든 조건을 만족하기 때문에 비밀번호로 사용할 수 있다.

 

민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분분자열의 길이, 그리고 {‘A’, ‘C’, ‘G’, ‘T’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

입력

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

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

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

출력

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

 

예제 입력 1 

9 8
CCTGGATTG
2 0 1 1

예제 출력 1 

0

 

예제 입력 2 

4 2
GATA
1 0 0 1

예제 출력 2 

2

 

 

 

 

Solution

 

<문제 분석>

dna 배열이 1,000,000으로 길기 때문에 O(n)의 시간 복잡도 알고리즘으로 풀어야한다.

부분 문자열의 길이만큼 비교하면 되기 때문에 슬라이딩 윈도우를 이용하였다.

 

슬라이딩 윈도우란?
2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동하며 해결한다.

 

 

직접 그리면서 예시를 풀어봤는데, 입력받은 최소 개수를 갖는 배열을 검사 배열로 한다.

이때, 4개의 알파벳과 그에 따른 최소 개수만 넘으면 count를 하나 증가시킨다 이 count 변수 값이 4가 되면 정답으로 하는 식으로 하고자 했다. 

하지만 문제가 "최소"개수인 점이었다. 그래서 add함수를 구현할 때 하나씩 알파벳을 추가하면서 해당 개수를 증가시킨 뒤, 최소 개수와 비교했다.  이미 최소 개수와 같은 시점에서 count를 증가시키면 되면 최소의 조건을 충족하기 때문이다.

또한, 최소 개수 자체가 0이면 어떤 수여도 만족하기 때문에 최소 개수가 0인만큼 count를 먼저 증가시켰다.

 

반대로 remove함수에서는 최소개수를 유지한 상태라면 하나를 감소시키고 개수를 감소시켰다.

 

다음으로 어려웠던 점은 슬라이싱 윈도우를 for문으로 구현할 때였다.

이미 첫 번째 배열은 있는 상태이기 때문에 그다음 인덱스를 추가하고 맨 앞의 인덱스를 제거하면 되었다.

말은 쉬웠는데 i의 범위를 많이 고민했다.

단순하게 1개의 부분문자열이 끝나는 인덱스는 m이기 때문에 여기서부터 i의 범위를 시작하고,

대신 제거하는 범위는 맨 처음 인덱스여야 하기 때문에 i-m으로 나타내었다.

 

이 문제의 포인트는 

 

기존 검사한 것을 기준으로
새로 들어오고 나가는 숫자만
업데이트해주자!
  

라고 생각하고 풀었다.

 

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

public class Main {
    //입력받은 각 문자의 최소 개수를 저장하는 배열 (A, C, G, T 순서)
    static int checkArr[];
    //현재 슬라이딩 윈도우에서 각 문자의 개수를 저장하는 배열
    static int test[];
    //조건을 만족하는 문자의 개수를 카운트
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //첫번째 줄로 입력받은 변수 두개 저장
        int n = Integer.parseInt(st.nextToken());//DNA 문자열의 길이
        int m = Integer.parseInt(st.nextToken());//검사할 부분 문자열의 길이

        // DNA 문자열을 저장하는 배열
        char dna[] = new char[n];
        checkArr = new int[4];
        test = new int[4];
        int answer = 0;//조건을 만족하는 부분 문자열의 수
        count = 0;

        //두번째줄로 입력받은 dna 문자열을 배열로 저장
        dna = br.readLine().toCharArray();
        //세번째줄로 입력받은 4개의 숫자 저장
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if(checkArr[i] == 0) {
                count++;
            }
        }

        //초기 윈도우 설정
        for(int i = 0; i <m; i++) {
            Add(dna[i]);
        }
		//초기 윈도우에서 답이 나올경우 
        if(count == 4) {
            answer++;
        }
        // 슬라이딩 윈도우를 이용해 문자열 검사
        for(int i = m; i<n; i++) {
            Add(dna[i]);
            Remove(dna[i-m]);
            if(count == 4){
                answer++;
            }

        }
        System.out.println(answer);
        br.close();
    }
    // 윈도우에 문자를 추가하는 함수
    public static void Add(char c) {
        switch (c){
            case 'A':
                test[0]++;
                if(test[0] == checkArr[0]) {
                    count++;
                }
                break;
            case 'C':
                test[1]++;
                if(test[1] == checkArr[1]) {
                    count++;
                }
                break;
            case 'G':
                test[2]++;
                if(test[2] == checkArr[2]) {
                    count++;
                }
                break;
            case 'T':
                test[3]++;
                if(test[3] == checkArr[3]) {
                    count++;
                }
                break;
        }
    }
    // 윈도우에서 문자를 제거하는 함수
    public static void Remove(char c) {
        switch (c){
            case 'A':
                if(test[0] == checkArr[0]) {
                    count--;
                }
                test[0]--;
                break;
            case 'C':
                if(test[1] == checkArr[1]) {
                    count--;
                }
                test[1]--;
                break;
            case 'G':
                if(test[2] == checkArr[2]) {
                    count--;
                }
                test[2]--;
                break;
            case 'T':
                if(test[3] == checkArr[3]) {
                    count--;
                }
                test[3]--;
                break;
        }
    }
}