백준 [12891] DNA 비밀번호 (자바)

문제

입력

 

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

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

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

출력

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

풀이

S - P 만큼 뺀 만큼 반복을 하면서 부분 배열을 탐색하려고 했는데 브루트 포스와 슬라이딩 윈도우 개념이 헷갈렸었다.

 

100만까지 입력이 들어와서 브루트 포스로 탐색을 할 경우 시간초과가 발생했다.

 

투 포인터/슬라이딩 윈도우 알고리즘으로 해결

1. 처음 0 ~ P (부분 비밀번호 배열)까지 DNA 문자 개수를 체크하고 유효성 검사를 한다.
2. 그 다음 j = P 부터 S 까지 i = j - P 로 두면 i 는 부분 문자열의 처음, j는 부분 문자열의 끝으로 둔다.
3. 제일 왼쪽(i)에 해당하는 문자를 카운트한 갯수를 뺀다.
4. 제일 오른쪽(j)에 해당하는 문자를 카운트한 갯수를 더한다.
5. 부분 배열이 비밀번호의 최소 개수를 만족하는지 검사하고 만족하면 카운트한다.

정답코드

package com.baekjoon.p12891;

import java.io.*;
import java.util.*;

public class Main {
    static int[] minCnt = new int[4], acgt = 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());

        String str = br.readLine();

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

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

        int ans = 0;

        for (int i = 0; i < P; i++) {
            if (str.charAt(i) == 'A') {
                acgt[0]++;
            } else if (str.charAt(i) == 'C') {
                acgt[1]++;
            } else if (str.charAt(i) == 'G') {
                acgt[2]++;
            } else if (str.charAt(i) == 'T') {
                acgt[3]++;
            }
        }

        if (valid()) {
            ans++;
        }

        int i = -1;

        for (int j = P; j < S; j++) {
            i = j - P;

            if (str.charAt(i) == 'A') {
                acgt[0]--;
            } else if (str.charAt(i) == 'C') {
                acgt[1]--;
            } else if (str.charAt(i) == 'G') {
                acgt[2]--;
            } else if (str.charAt(i) == 'T') {
                acgt[3]--;
            }

            if (str.charAt(j) == 'A') {
                acgt[0]++;
            } else if (str.charAt(j) == 'C') {
                acgt[1]++;
            } else if (str.charAt(j) == 'G') {
                acgt[2]++;
            } else if (str.charAt(j) == 'T') {
                acgt[3]++;
            }

            if (valid()) {
                ans++;
            }
        }

        System.out.println(ans);
    }

    static boolean valid() {
        for (int i = 0; i < 4; i++) {
            if (acgt[i] < minCnt[i]) {
                return false;
            }
        }
        return true;
    }
}

 

다른 풀이

package com.baekjoon.p12891;

import java.io.*;
import java.util.*;

public class Main {
    static int[] minCnt = new int[4], acgt = 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());

        String str = br.readLine();

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

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

        int ans = 0;

		// 임시 비밀번호 갯수 카운트
        for (int i = 0; i < P; i++) {
            if (str.charAt(i) == 'A') {
                acgt[0]++;
            } else if (str.charAt(i) == 'C') {
                acgt[1]++;
            } else if (str.charAt(i) == 'G') {
                acgt[2]++;
            } else if (str.charAt(i) == 'T') {
                acgt[3]++;
            }
        }

        for (int i = 0; i <= S - P; i++) {
            if (valid()) { // 카운트 했던 임시 비밀번호가 유효한지 체크
                ans++;
            }

            if (i == S - P) {
                break;
            }

            acgt[position(str.charAt(i))]--; // 제일 앞쪽 비밀번호를 뺀다.
            acgt[position(str.charAt(i + P))]++; // 제일 뒤쪽 비밀번호를 더한다.
        }

        System.out.println(ans);
    }

	// 비밀번호가 유효한지 검사
    static boolean valid() {
        for (int i = 0; i < 4; i++) {
            if (acgt[i] < minCnt[i]) {
                return false;
            }
        }
        return true;
    }
	
    // 해당 비밀번호 문자의 위치를 반환
    static int position(char target) {
        if (target == 'A') {
            return 0;
        } else if (target == 'C') {
            return 1;
        } else if (target == 'G') {
            return 2;
        }

        return 3;
    }
}