JAVA 백준 12891 DNA 비밀번호 (슬라이딩 윈도우)

gamja00 2025. 5. 31. 20:40

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

문제

첫째 줄에 DNA 문자열의 길이 | S |와 비밀번호로 사용할 부분 문자열의 길이 | P | ( 1 <= | P | <= | S | <= 1000000 ) 이 입력된다.
둘째 줄에 임의의 DNA이 입력된다.
셋째 줄에 부분 문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백으로 구분되어 입력된다. 각각의 수는 | S | 보다 작거나 같은 음이 아닌 정수이며, 네 개의 수의 총합은 | S | 보다 작거나 같다.

초기 코드 (시간 초과)

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

public class Main {
    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());

        String[] dna = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        int[] list = new int[4];
        for (int i = 0; i < 4; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;

        for (int i = 0; i <= S - P; i++) {
            boolean flag = true;
            HashMap<String, Integer> map = new HashMap<>();

            for (int j = i; j < i + P; j++) {
                map.put(dna[j], map.getOrDefault(dna[j], 0) + 1);
            }

            if (map.getOrDefault("A", -1) < list[0]) {
                flag = false;
            }
            if (map.getOrDefault("C", -1) < list[1]) {
                flag = false;
            }
            if (map.getOrDefault("G", -1) < list[2]) {
                flag = false;
            }
            if (map.getOrDefault("T", -1) < list[3]) {
                flag = false;
            }

            if (flag) {
                count++;
            }
        }

        System.out.println(count);
    }
}

HashMap을 이용한 코드.
HashMap<String, Integer>를 만들어 Key에 A, C, G, T를 넣고 Value에 슬라이딩 윈도우 범위 내의 문자를 하나씩 세면서 Key와 같다면 Value를 하나씩 증가시킨다.
이후 HashMap에 있는 값이 입력된 조건에 부합하면 최종 정답으로 출력할 변수를 1 증가시킨다.

모든 범위를 여러 번 확인해서 오래 걸리는 것 같다.
재사용하고 줄여 사용해야겠다.

성공한 코드... 긴 한데 너무 오래 걸리는 것 같다

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

public class Main {
    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());

        String[] dna = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        int[] list = new int[4];
        for (int i = 0; i < 4; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }

        int count = 0;
        int window = 0;

        HashMap<String, Integer> map = new HashMap<>();

        for (int i = 0; i <= S - P; i++) {
            boolean flag = true;

            if (window == 0) {
                int temp = window;
                for (int j = i; j < i + P - temp; j++) {
                    map.put(dna[j], map.getOrDefault(dna[j], 0) + 1);
                    window++;
                }
            } else {
                map.put(dna[i +  window], map.getOrDefault(dna[i +  window], 0) + 1);
                window++;
            }

            if (map.getOrDefault("A", 0) < list[0] ||
                    map.getOrDefault("C", 0) < list[1] ||
                    map.getOrDefault("G", 0) < list[2] ||
                    map.getOrDefault("T", 0) < list[3]) {
                flag = false;
            }

            if (flag) {
                count++;
            }

            map.put(dna[i], map.get(dna[i]) - 1);
            window--;
        }

        System.out.println(count);
    }
}

HashMap을 사용해서 그런지 시간이 오래 걸리는 것 같다.
다른 방법을 이용해서도 정답을 구해봐야겠다.

최종 코드 (시간이 많이 줄은 코드)

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

public class Main {
    public static int result = 0;
    public static int index = 0;

    public static void checkList(String[] dna, int[] list, int[] check) {
        boolean flag = true;

        for (int i = 0; i < 4; i++) {
            if (list[i] < check[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            result++;
        }

        switch (dna[index]) {
            case "A":
                list[0]--;
                break;
            case "C":
                list[1]--;
                break;
            case "G":
                list[2]--;
                break;
            case "T":
                list[3]--;
                break;
        }
        index++;
    }

    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());

        String[] dna = br.readLine().split("");

        st = new StringTokenizer(br.readLine());
        int[] check = new int[4];
        for (int i = 0; i < 4; i++) {
            check[i] = Integer.parseInt(st.nextToken());
        }

        int[] list = new int[4];

        for (int i = 0; i < S; i++) {
            switch (dna[i]) {
                case "A":
                    list[0]++;
                    break;
                case "C":
                    list[1]++;
                    break;
                case "G":
                    list[2]++;
                    break;
                case "T":
                    list[3]++;
                    break;
            }
            if (i >= P - 1) {
                checkList(dna, list, check);
            }
        }

        System.out.println(result);
    }
}

HashMap이 아닌 int 배열을 이용하여 입력된 조건과 비교하는 방식이다.
메인 코드가 많이 길어질 것 같아 함수를 이용했다.