[슬라이딩 윈도우] DNA 비밀번호

목차

1. 풀이

(1) 문제

백준 12891번, DNA 비밀번호 : https://www.acmicpc.net/problem/12891

 

핵심 키워드

1) 문제

- 시간 제한 2초

- DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다.

- 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다는 규칙이 있다.

 -> ex) 부분문자열에 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상일 때, 

 -> "AAAA" (x) , "ACGA" (0) 

 -> 임의의 DNA문자열이 “AAACCTGCCAA” 이고 민호가 뽑을 부분문자열의 길이를 4라고 하는 조건 추가한다면

 -> "AAAC (x) , AACC(x),  ..., GCCA(O)

 

2) 입력

- 첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 |S|와 비밀번호로 사용할 부분문자열의 길이.

  -> |P| (1 ≤ |P| ≤ |S| ≤ 1,000,000)

- 두번 째 줄에는 민호가 임의로 만든 DNA 문자열

- 세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다.

  -> 각각의 수는 |S| 보다 작거나 같은 음이 아닌 정수이며 총 합은 |S| 보다 작거나 같음이 보장

 

3) 출력

- 비밀번호 종류의 수를 출력

 

(2) 풀이

1) 투 포인터 활용하여 순차적으로 일일이 문자열을 체크하는 방법

• 이 방법은 시간복잡도가 O(n²)이기 때문에 시간 제한초과이므로 이 문제의 정답은 아니다.
• 그러나 조건의 크기가 1000이하라면 총 연산 횟수는 1000 * 1000 = 10만이므로 충분히 가능하다.
• 개인적으로 뒤에 나오는 슬라이딩 윈도우 알고리즘보다 더 직관적이고 이해하기 쉬운 방법이라 생각한다.
• EX) 첫째 줄 입력 5 3, 둘째 줄 입력 GATAC, 셋째 줄 입력 1 1 0 1 일 때 풀이

• 코드

import java.io.IOException;
import java.util.Scanner;

public class DNA비밀번호_1 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int P = sc.nextInt();
        String dna = sc.next();
        int[] N = new int[4];

        for (int i = 0; i < 4; i++) {
            N[i] = sc.nextInt();
        }

        int start = 0;
        int end = P;
        int count = 0;


        char[] charArray = dna.toCharArray();
        while (end <= S) {
            int aCount = 0; // 구간 반복될 때마다 0으로 초기화
            int cCount = 0;
            int gCount = 0;
            int tCount = 0;

            for (int i = start; i < end; i++) { // start 가 end 까지 이동하면서 반복
                switch (charArray[i]) { // 문자와 일치하는 case 에 count
                    case 'A' : aCount++; break;
                    case 'C' : cCount++; break;
                    case 'G' : gCount++; break;
                    case 'T' : tCount++; break;
                }
            }
            // 부분문자열 조건과 탐색한 구간의 숫자개숫를 비교하여 조건 만족시 count 숫자를 더해준다.
            if ( N[0] >= aCount && N[1] >= cCount && N[2] >= gCount && N[3] >= tCount ) {
                count++;
            }

            // 구간 검색이 끝났으면 start와 end를 한칸 씩 오른쪽으로 이동
            start++;
            end++;
        }
        System.out.println(count);
    }
}

 

2) 슬라이딩 윈도우를 활용하여 푸는 방법

• 투 포인트를 활용하는 것은 똑같다. 하지만 단순히 투 포인트를 썼을 때는 일일히 문자열을 체크하는 방법이었다면, 이 방법은 범위 이동을 통해 중간에 있는 문자열은 체크하지 않고 처음 부분은 제거하고 끝 부분을 추가해서 체크하는 방법이다. 
• 중간 부분은 체크하지 않고 처음과 끝 부분만 체크하기 때문에 시간복잡도가 O(n)이다.

2. 정답

슬라이딩 윈도우 적용

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

public class P12891_DNA비밀번호 {
    static int[] myArr = new int[4]; // 현재 상태 배열
    static int[] checkArr = new int[4]; // 비밀번호 체크 배열
    static int checkSecret = 0; // 비밀번호 체크 배열 만족여부 변수, 4이면 모두 만족

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine()); // 첫번째줄 입력 값 받음
        int S = Integer.parseInt(st.nextToken()); // DNA 문자열 길이
        int P = Integer.parseInt(st.nextToken()); // 비밀번호로 사용할 부분문자열의 길이
        int result = 0; // 조건에 만족하는 비밀번호 개수
        char[] A; // DNA 문자열

        A = bf.readLine().toCharArray(); // 두번째 줄 입력값 char[]로 일일이 문자를 저장
        st = new StringTokenizer(bf.readLine()); // 3번째 줄 입력값 받음
        for (int i = 0; i < 4; i++) {
            // 비밀번호 체크 배열에 세번째 줄 입력값 저장
            checkArr[i] = Integer.parseInt(st.nextToken());
            if ( checkArr[i] == 0) { // 만약 입력값에 0이 있다면 +1를 한다.
                checkSecret++;
            }
        }

        // 부분문자열 처음 받을 때 세팅
        for(int i=0; i<P; i++) {
            add(A[i]);
        }

        // 처음 받을 때 조건 성립 여부 확인
        if (checkSecret == 4) { // 4이면 모든 조건에 만족한다는 의미
            result++;
        }

        // 슬라이딩 윈도우
        for(int end = P; end < S; end++) { // end 가 DNA 문자열길이에 도달할 떄까지
            // start = end - 부분문자열 길이, 즉 검색범위 왼쪽 끝 바로 옆(왼쪽)에 위치함.
            int start = end - P;
            add(A[end]); // end 문자 추가후 체크
            remove(A[start]); // start  문자 제거후 체크

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

        System.out.println(result);
        bf.close();
    }

    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;
        }
    }

    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;
        }
    }
}

- 처음 구간에서 일일이 체크, 그 후 슬라이딩 윈도우 적용

- 현재 상태 배열과 비밀번호 체크 배열을 비교해서 조건 성립하는 지 체크.

3. 참고

- Do it 알고리즘 코딩 테스트 자바 편(김종관)