[JAVA] 백준 : DNA 비밀번호

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

처음 코드

이 코드는 코드의 로직 상 문제는 없으나, 시간 초과가 떴다. 모든 문자열을 다 비교해보기 때문인 것 같다ㅠㅠ 인터넷을 찾아보니 '슬라이딩 윈도우'로 풀어야 한다고 한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int s = Integer.parseInt(input[0]); //임의로 만든 문자열 길이
        int p = Integer.parseInt(input[1]); //비밀번호로 사용할 부분문자열 길이
        String dna = br.readLine();
        String[] nums = br.readLine().split(" ");
        int aCnt = Integer.parseInt(nums[0]);
        int cCnt = Integer.parseInt(nums[1]);
        int gCnt = Integer.parseInt(nums[2]);
        int tCnt = Integer.parseInt(nums[3]);
        int cnt = 0;
        //입력된 문자열이 특정 개수 이상이어야 함
        //dna에 있는 글자여야 함
        String answer = "";
        //일단 부분 문자열 구하기
        int a = 0;
        int c = 0;
        int g = 0;
        int t = 0;
        for (int i = 0; i <= s - p; i++) {
            answer = dna.substring(i, i+p);
            
            for(int j=0; j<answer.length(); j++){
                if(answer.charAt(j) == 'A'){
                    a++;
                }
                if(answer.charAt(j) == 'C'){
                    c++;
                }
                if(answer.charAt(j) == 'G'){
                    g++;
                }
                if(answer.charAt(j) == 'T') {
                    t++;
                }
            }
            if(a >= aCnt && c >= cCnt && g >= gCnt && t >= tCnt){
                cnt ++;
            }
        }
        System.out.println(cnt);
        br.close();
    }
}

정답 코드

package silver2;

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

public class num12891 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int s = Integer.parseInt(input[0]); // 전체 문자열 길이
        int p = Integer.parseInt(input[1]); // 비밀번호로 사용할 부분 문자열 길이
        String dna = br.readLine();
        String[] nums = br.readLine().split(" ");
        int aCnt = Integer.parseInt(nums[0]);
        int cCnt = Integer.parseInt(nums[1]);
        int gCnt = Integer.parseInt(nums[2]);
        int tCnt = Integer.parseInt(nums[3]);
        int cnt = 0;

        int[] currentCount = new int[4];

        for (int i = 0; i < p; i++) {
            char ch = dna.charAt(i);
            if (ch == 'A') currentCount[0]++;
            if (ch == 'C') currentCount[1]++;
            if (ch == 'G') currentCount[2]++;
            if (ch == 'T') currentCount[3]++;
        }

        // 첫 번째 윈도우가 조건을 만족하는지 확인
        if (currentCount[0] >= aCnt && currentCount[1] >= cCnt && currentCount[2] >= gCnt && currentCount[3] >= tCnt) {
            cnt++;
        }

        // 슬라이딩 윈도우로 나머지 부분 문자열 검사
        for (int i = p; i < s; i++) {
            // 윈도우에서 벗어나는 문자 제거
            char chOut = dna.charAt(i - p);
            if (chOut == 'A') currentCount[0]--;
            if (chOut == 'C') currentCount[1]--;
            if (chOut == 'G') currentCount[2]--;
            if (chOut == 'T') currentCount[3]--;

            // 윈도우에 새로 들어오는 문자 추가
            char chIn = dna.charAt(i);
            if (chIn == 'A') currentCount[0]++;
            if (chIn == 'C') currentCount[1]++;
            if (chIn == 'G') currentCount[2]++;
            if (chIn == 'T') currentCount[3]++;
            
            if (currentCount[0] >= aCnt && currentCount[1] >= cCnt && currentCount[2] >= gCnt && currentCount[3] >= tCnt) {
                cnt++;
            }
        }

        System.out.println(cnt);
        br.close();
    }
}