[JAVA] DNA 비밀번호 - 백준 12891번

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

 

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    private static boolean check_map(Map<Character, Integer> map){
        for(char key : map.keySet()){
            if(map.get(key) > 0){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(input.readLine());

        int s = Integer.parseInt(st.nextToken());
        int p = Integer.parseInt(st.nextToken());
        int answer = 0;
        String str = input.readLine();

        Map<Character, Integer> map = new HashMap<>();
        char[] dna = {'A', 'C', 'G', 'T'};
        st = new StringTokenizer(input.readLine());
        for(int i =0; i<4; i++){
            map.put(dna[i], Integer.parseInt(st.nextToken()));
        }
        Queue<Character> queue = new LinkedList<>();
        // 첫 윈도우에 대해서 연산 수행
        for(int i = 0; i<p; i++){
            char c = str.charAt(i);
            queue.add(c);
            map.put(c, map.get(c)-1);
        }
        if(check_map(map))answer++;


        for(int i = p; i<s; i++){
            char removeChar = queue.poll(); // 윈도우의 맨 앞글자 제거
            if(map.containsKey(removeChar)){
                map.put(removeChar, map.get(removeChar)+1);
            }
            char c = str.charAt(i);
            queue.add(c);
            if(map.containsKey(c)){
                map.put(c, map.get(c) -1);
                if(check_map(map)){
                    answer++;
                }
            }

        }
        System.out.println(answer);
    }
}

슬라이딩 윈도우를 활용하여 해결하였다.

HashMap에 문제에서 요구하는 ACGT에 대한 최소치를 입력해두고

윈도우를 이동해가면서 해당 수치를 변화 시켜주었다. 만약 ACGT중 하나가 윈도우에 들어오면 감소시키고 빠져나가면 증가시키는 방식이다.

윈도우를 옮길때마다 HashMap을 체크하여 모든 값들이 0 이라면 통과