[JAVA][Baekjoon] 12891번 DNA 비밀번호 ⭐️

12891번: DNA 비밀번호

---

📌 슬라이딩 윈도우

• 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 해결하는 것

📌 접근 방법

• 슬라이딩 윈도우를 사용해서 범위를 4칸으로 유지한 채 한 칸씩 이동하며 배열의 상태를 업데이트 해준다.
• 배열을 업데이트 할 때는 앞에 빠지는걸 빼고 뒤에거를 추가시키는 식으로 업데이트!
• A, C, G, T 의 개수를 담고있는 배열과 비교하면서 판단

 

 

🚨 시간 초과 코드

import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static int[] arr = {0, 0, 0, 0};
    public static void main(String [] args) throws IOException {

       Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        int P = sc.nextInt();

        String str = sc.next();
        int[] checkArr = new int[4];

        for (int i = 0; i < 4; i++) {
            checkArr[i] = sc.nextInt();
        }
        int cnt = 0;

        for(int i=0; i<=S-P; i++){
            for(int j=i; j<i+P; j++){
                add(str.charAt(j));
            }

            if(checkArr[0]<=arr[0] && checkArr[1]<=arr[1] && checkArr[2]<=arr[2] && checkArr[3]<=arr[3]  ){
                cnt++;
            }
            arr[0]=0;
            arr[1]=0;
            arr[2]=0;
            arr[3]=0;
        }

        System.out.println(cnt);
    }
    private static void add(char c){
        if(c =='A'){
           arr[0] ++;
        }
        else if(c =='C'){
            arr[1] ++;
        }
        else if(c =='G'){
            arr[2] ++;
        }
        else if(c =='T'){
            arr[3] ++;
        }
    }
}

✅ PASS CODE

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

public class Main {
    private static int[] arr = {0, 0, 0, 0};
    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 str = br.readLine().toString();

        st = new StringTokenizer(br.readLine());

        int [] checkArr = new int[4];

        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
        }
        int cnt = 0;

        for(int i=0; i<P; i++){
            add(str.charAt(i));
        }
        if(isSuccess(arr, checkArr)){
            cnt++;
        }
        for(int i=P; i<S; i++){
            remove(str.charAt(i-P));
            add(str.charAt(i));
            if(isSuccess(arr, checkArr)){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
    private static void add(char c){
        if(c =='A'){
           arr[0] ++;
        }
        else if(c =='C'){
            arr[1] ++;
        }
        else if(c =='G'){
            arr[2] ++;
        }
        else if(c =='T'){
            arr[3] ++;
        }
    }
    private static void remove(char c){
        if(c =='A'){
            arr[0] --;
        }
        else if(c =='C'){
            arr[1] --;
        }
        else if(c =='G'){
            arr[2] --;
        }
        else if(c =='T'){
            arr[3] --;
        }
    }
    private static boolean isSuccess(int []arr, int[]checkArr){
        if(checkArr[0]<=arr[0] && checkArr[1]<=arr[1] && checkArr[2]<=arr[2] && checkArr[3]<=arr[3]  ){
            return true;
        }
        return false;
    }
}

• 시간초과가 나서 다시 구현해보았다...
• 우선 P 만큼의 배열만큼 나눠서 생각했고, 한 칸 뒤로 갈 때마다 i-P로 앞에 것을 빼고 뒤에 것을 추가하는 식으로 반복문을 줄여 시간초과를 해결했다!