[백준, 12891] DNA 비밀번호

문제

 

DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다.

 

임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용한다.

단, 부분문자열에서 등장하는 문자의 개수가 특정 개수 이상이여야 비밀번호로 사용할 수 있다

그리고 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.

 

 

부분 문자열의 길이는 고정적이기 때문에 일정 간격으로 옮겨가면서 비밀번호가 될 수 있는지 체크를 해야 한다.

슬라이딩 윈도우로 푼다.

 

슬라이딩 윈도우를 한칸씩 움직이면서 left 문자를 빼주고 right 문자를 더해주는 식으로 하면 문자열마다 A, C, G, T 문자를 새로 구할 필요가 없다.

 

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

import static java.lang.System.in;

public class Main {
    public static void main(String[] args) throws IOException {
        final BufferedReader br = new BufferedReader(new InputStreamReader(in));
        final StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int S = Integer.parseInt(st.nextToken());
        int P = Integer.parseInt(st.nextToken());

        final char[] dnaCharacters = br.readLine().toCharArray();

        st = new StringTokenizer(br.readLine());
        DnaPassword password = new DnaPassword(
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken()),
                Integer.parseInt(st.nextToken())
        );

        int lt = 0;
        int rt = 0;
        int count = 0;

        while (rt < P) {
            password.add(dnaCharacters[rt++]);
        }

        while (rt < dnaCharacters.length) {
            if (password.canCreatePassword()) {
                ++count;
            }
            password.remove(dnaCharacters[lt++]);
            password.add(dnaCharacters[rt++]);
        }

        if (password.canCreatePassword()) {
            ++count;
        }

        System.out.println(count);
    }

    static class DnaPassword {
        final int[] standardCounts;
        final int[] countOfcharacter = new int[4];

        DnaPassword(int A, int C, int G, int T) {
            standardCounts = new int[]{A, C, G, T};
        }

        public void add(char ch) {
            countOfcharacter[indexOf(ch)] += 1;
        }

        public void remove(char ch) {
            countOfcharacter[indexOf(ch)] -= 1;
        }

        private int indexOf(char ch) {
            if (ch == 'A') {
                return 0;
            }
            if (ch == 'C') {
                return 1;
            }
            if (ch == 'G') {
                return 2;
            }
            if (ch == 'T') {
                return 3;
            }

            throw new IllegalArgumentException();
        }

        public boolean canCreatePassword() {
            return standardCounts[0] <= countOfcharacter[0] &&
                    standardCounts[1] <= countOfcharacter[1] &&
                    standardCounts[2] <= countOfcharacter[2] &&
                    standardCounts[3] <= countOfcharacter[3];
        }
    }
}