백준 알고리즘 - 12891번: DNA 비밀번호 [Java]

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

12891번: DNA 비밀번호

1. 코드

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

public class Main {
    static int answer;
    static String[] DNA = {"A", "C", "G", "T"};
    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());

        Map<String, Integer> check = new HashMap<>();
        Map<String, Integer> current = new HashMap<>();
        String[] str = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        for(String s : DNA) {
            check.put(s, Integer.parseInt(st.nextToken()));
            current.put(s, 0);
        }

        for(int i = 0; i < P; i++)
            current.put(str[i], current.get(str[i]) + 1);
        valid(current, check);

        for(int i = 1; i <= str.length - P; i++) {
            current.put(str[i - 1], current.get(str[i - 1]) - 1);
            current.put(str[i + P - 1], current.get(str[i + P - 1]) + 1);
            valid(current, check);
        }
        System.out.println(answer);
        br.close();
    }

    private static void valid(Map<String, Integer> current, Map<String, Integer> check) {
        for(String s : DNA) {
            if(current.get(s) < check.get(s))
                return;
        }
        answer++;
    }
}

2. 설명

슬라이딩 윈도우를 사용하여 문제를 풀었다.

        Map<String, Integer> check = new HashMap<>();
        Map<String, Integer> current = new HashMap<>();

check는 DNA 문자열에 대한 규칙 그리고 current는 현재 윈도우의 상태를 저장한다.

    static int answer;
    static String[] DNA = {"A", "C", "G", "T"};
    private static void valid(Map<String, Integer> current, Map<String, Integer> check) {  
        for(String s : DNA) {
            if(current.get(s) < check.get(s))
                return;
        }
        answer++;
    }

valid 함수를 통해서 current가 DNA 문자열에 적합한지 확인하며 적합하면 answer의 값을 증가시킨다.

        for(int i = 0; i < P; i++)
            current.put(str[i], current.get(str[i]) + 1);
        valid(current, check);

        for(int i = 1; i <= str.length - P; i++) {
            current.put(str[i - 1], current.get(str[i - 1]) - 1);
            current.put(str[i + P - 1], current.get(str[i + P - 1]) + 1);
            valid(current, check);
        }

일단 P크기만큼의 문자열에 대한 정보를 current에 갱신한 뒤 검사를 진행하며 반복문을 통해서 나가는 문자열에 해당하는 것은 -1을 들어오는 문자열에 해당하는 것은 +1을 하여 슬라이딩 하면서 윈도우를 갱신한다. 그리고 검사를 진행한 뒤 answer를 출력하면 된다.

3. 정리

슬라이딩 윈도우와 HashMap을 통해서 쉽게 해결할 수 있었다.