[BJ]S2_12891_DNA문자열

BJ_S2_12891_DNA문자열

 

 

문제링크

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

12891번: DNA 비밀번호

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

https://youtu.be/UL0g9xMs61E

- YouTube

 

 

소스보기

동영상 설명을 보고도 전혀 구현이 안된다면 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.silver.l2;

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

/**
 * @author 은서파
 * @since 2022. 7. 8.
 * @see https://www.acmicpc.net/problem/12891
 * @git https://github.com/quietjun/algo_aps/blob/master/src/bj/silver/l2/BJ_S2_12891_DNA%EB%AC%B8%EC%9E%90%EC%97%B4.java
 * @youtube  
 * @performance     19776   184
 * @category #슬라이딩윈도
 * @note 부분문자열: 주어진 문자열의 중간에 있는 연속된 부분문자열. 
 * 매번 부분 문자열을 새로 점검하면 시간 복잡도가 P*S,
 * 슬라이딩 윈도우를 적용하면 P 
 */

public class BJ_S2_12891_DNA문자열 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder output = new StringBuilder();
    static StringTokenizer tokens;
    
    static int P, S;
    static String STR;
    static int [] CHAR_CNT = new int['Z'+1];
    static int A, C, G, T;
    static int PASS_CNT;
    
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        P = Integer.parseInt(tokens.nextToken());
        S = Integer.parseInt(tokens.nextToken());
        STR = input.readLine();
        tokens = new StringTokenizer(input.readLine());
        A = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());
        G = Integer.parseInt(tokens.nextToken());
        T = Integer.parseInt(tokens.nextToken());
        
        // 초기 윈도우 배치
        PASS_CNT = 0;
        for(int s=0; s<S; s++) {
            CHAR_CNT[STR.charAt(s)]++;
        }
        if(isPossible()) {
            PASS_CNT++;
        }
        
        // 윈도우 슬라이딩
        for(int s=S; s<P; s++) {
            CHAR_CNT[STR.charAt(s-S)]--;// 맨 앞에꺼는 하나 뺌
            CHAR_CNT[STR.charAt(s)]++;// 이번꺼는 넣음
            if(isPossible()) {
                PASS_CNT++;
            }
        }
        System.out.println(PASS_CNT);
    }
    
    private static boolean isPossible() {
        return CHAR_CNT['A']>=A && CHAR_CNT['C']>=C && CHAR_CNT['G']>=G && CHAR_CNT['T']>=T;
    }

    // REMOVE_START
    private static String src = "4 2\n"
            + "GATA\n"
            + "1 0 0 1";
    // REMOVE_END

}