백준 12891 - DNA 비밀번호

문제 파악

A, C, G, T로만 이루어진 문자열이 DNA 문자열
길이가 S인 문자열에서 길이가 P인 부분 문자열을 추출해 비밀번호를 만들 것인데, 이 문자열 안에 포함된 A, C, G, T의 개수가 주어진 조건 이상이어야 유효한 비밀번호로 인정된다. 이 유효한 비밀번호가 몇 개 나오는지를 찾는 문제

슬라이딩 윈도우 : 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀 수 있는 알고리즘

길이 P만큼의 문자열을 초기 윈도우로 만들고 A, C, G, T의 각각 개수를 세고 조건에 맞는지 판단한 후 왼쪽 문자를 제거하고 오른쪽 문자를 추가하면서 오른쪽으로 한 칸씩 이동하면서 조건을 만족하는지 판단한다. -> 매번 새로 세는 것 보다 들어온 문자와 나간 문자만 업데이트하게 되어 훨씬 효율적!

풀이

1. 버퍼리더와 스트링토크나이저를 사용해 입력받을 문자열 개수 S와 부분 문자열 길이 P를 입력받는다.
2. DNA 문자열을 입력받는다.
3. A, C, G, T의 최소 개수를 입력받아 배열에 집어 넣는다.
4. 초기 윈도우 내에서 A, C, G, T의 개수를 저장할 배열을 만든다.
5. 초기 윈도우에서 개수를 세고 조건에 맞는지 판단한다.
   a. 조건을 만족하면 카운트
   b. 왼쪽 문자열 제거, 오른쪽 문자열 추가해서 다시 검사

코드

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

public class DNA_비밀번호 {

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

        //입력받을 문자열 개수 S와 부분 문자열 길이 P
        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        //DNA 문자열 입력력
        String dna = bf.readLine();

        StringTokenizer st2 = new StringTokenizer(bf.readLine());
        //A, C, G, T 최소 개수 조건 입력
        int[] minCount = new int[4];
        for (int i=0; i<4; i++) {
            minCount[i] = Integer.parseInt(st2.nextToken());
        }

        //현재 윈도우 상태 저장 배열
        int[] currentCount = new int[4];

        //초기 윈도우 문자열 세기
        //currentCount = [1, 2, 2, 3] 이런 식으로 입력됨(순서는 ACGT)
        for (int i=0; i<P; i++) {
            addChar(currentCount, dna.charAt(i));
        }

        //비밀번호 몇 개 가능한지 세는 변수
        int count = 0;
        if (isValid(currentCount, minCount)) {
            count++;
        }

        //슬라이딩 윈도우 수행
        for (int i=P; i<S; i++) {
            //초기 윈도우에서 빠질 문자
            //i=8일 때 i-P=0
            removeChar(currentCount, dna.charAt(i-P));
            //새로운 윈도우에서 추가될 문자
            addChar(currentCount, dna.charAt(i));
            if (isValid(currentCount, minCount)) {
                count++;
            }
        }
        System.out.println(count);
    }

    //슬라이딩 윈도우가 진행됨에 따라 빠지는 문자열을 계산해 줄 함수수
    static void removeChar(int[] count, char c) {
        switch (c) {
            case 'A':
                count[0]--;
                break;
            case 'C':
                count[1]--;
                break;
            case 'G':
                count[2]--;
                break;
            case 'T':
                count[3]--;
                break;
        }
    }

    //슬라이딩 윈도우가 진행됨에 따라 추가되는 문자열을 계산
    static void addChar(int[] count, char c) {
        switch (c) {
            case 'A':
                count[0]++;
                break;
            case 'C':
                count[1]++;
                break;
            case 'G':
                count[2]++;
                break;
            case 'T':
                count[3]++;
                break;
        }
    }

    //최소 조건에 만족하는지 아닌지 검사하는 함수
    static boolean isValid(int[] currentCount, int[] minCount) {
        for (int i=0; i<4; i++) {
            if (currentCount[i] < minCount[i]) {
                return false;
            }
        }
        return true;
    }
}