[백준] 12891 -자바

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

 

슬라이딩 윈도우를 사용해야하는 문제다.

첫 풀이때는 슬라이딩 윈도우를 사용하기는 하는데 정확하게 사용하지 않아 시간초과가 걸렸다.

---

시간초과 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        /*
        1.주어지는 문자열 s길이와 비밀번호 문자열 p길이를 받는다
        2.s문자열을 String으로 받는다
        3.StringTokenizer로 각 알파벳 최소개수를 받는다
        4.s문자열.toCharArray로 char배열로 만들고, 두 포인터를 p차이가 나도록 지정한다.
        5.엔드포인터가 s.length를 벗어나기까지 while반복 돌면서 for문을 돌아 알파벳 최소개수있는지 검사
         */


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int sLength =Integer.parseInt(st.nextToken());
        int pLength =Integer.parseInt(st.nextToken());
        String s = br.readLine();
        StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
        int aCount = Integer.parseInt(st2.nextToken());
        int cCount = Integer.parseInt(st2.nextToken());
        int gCount = Integer.parseInt(st2.nextToken());
        int tCount = Integer.parseInt(st2.nextToken());

        char[] sArr = s.toCharArray();
        int startPointer = 0;
        int endPointer = pLength-1;
        int answer =0;

        while(endPointer<=sLength-1){
            int aCheck =0;
            int cCheck =0;
            int gCheck =0;
            int tCheck =0;

            for(int i=startPointer; i<=endPointer; i++ ){
               if(sArr[i] =='A'){
                   aCheck++;
               } else if(sArr[i] == 'C'){
                   cCheck++;
               } else if(sArr[i] == 'G'){
                   gCheck++;
               } else if(sArr[i] == 'T'){
                   tCheck++;
               }
            }
          if(aCheck>=aCount && cCheck>=cCount && gCheck>=gCount && tCheck>=tCount){
              answer++;}
              startPointer++;
              endPointer++;

        }
        System.out.println(answer);

    }
}

 

두개의 포인터를 지정해 슬라이딩 윈도우를 사용하려고는 했는데 '슬라이딩' 하지않고 계속 for문을 돌았다...

윈도우 크기가 지정되고 한칸씩 이동하는 개념을 생각하면 이동할 때마다 기존의 시작점에 위치한 알파벳을 빼고 1칸 뒤로 밀린 엔드포인트에 위치한 알파벳이 들어오는 것만 확인해주면 되는걸 유념해서 아래와 같이 다시 풀었다.

---

정답

public class Main {
    public static void main(String[] args) throws IOException {
/*
        1.주어지는 문자열 s길이와 비밀번호 문자열 p길이를 받는다
        2.s문자열을 String으로 받는다
        3.StringTokenizer로 각 알파벳 최소개수를 받는다
        4.s문자열.toCharArray로 char배열로 만들고, 두 포인터를 p차이가 나도록 지정한다.
        5.일단 현재 위치한 슬라이드 윈도우 내에서 각 알파벳 개수가 몇개인지 체크한다.
        6.엔드포인터가 s.length를 벗어나기까지 while반복 윈도우를 이동시킨다.(두 포인터를 ++; 한다는 말)
        7.이때 슬라이드윈도우는 시작포인터가 한칸 오른쪽으로 이동하니 기존의 시작점에 있는 알파벳이 빠진다는 얘기고 엔드포인터도 한칸 오른쪽으로 이동하니 새로운 알파벳이 들어온다는 말.
        8.while반복도는 동안 개수 잘체크하면 된다
  */

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int sLength =Integer.parseInt(st.nextToken());
        int pLength =Integer.parseInt(st.nextToken());
        String s = br.readLine();
        StringTokenizer st2 = new StringTokenizer(br.readLine()," ");
        int aCount = Integer.parseInt(st2.nextToken());
        int cCount = Integer.parseInt(st2.nextToken());
        int gCount = Integer.parseInt(st2.nextToken());
        int tCount = Integer.parseInt(st2.nextToken());

        char[] sArr = s.toCharArray();
        int startPointer = 0;
        int endPointer = pLength-1;
        int answer =0;

        int aCheck =0;
        int cCheck =0;
        int gCheck =0;
        int tCheck =0;

        for(int i=startPointer; i<=endPointer; i++ ){
            if(sArr[i] =='A'){
                aCheck++;
            } else if(sArr[i] == 'C'){
                cCheck++;
            } else if(sArr[i] == 'G'){
                gCheck++;
            } else if(sArr[i] == 'T'){
                tCheck++;
            }
        }

        while(endPointer<=sLength-1){

          if(aCheck>=aCount && cCheck>=cCount && gCheck>=gCount && tCheck>=tCount){
              answer++;
          }

          if(sArr[startPointer]=='A'){
              aCheck--;
          } else if(sArr[startPointer]=='C'){
              cCheck--;
          } else if(sArr[startPointer]=='G'){
              gCheck--;
          } else if(sArr[startPointer]=='T'){
              tCheck--;
          }

              startPointer++;
              endPointer++;

         if(endPointer<=s.length()-1) {

             if (sArr[endPointer] == 'A') {
                 aCheck++;
             } else if (sArr[endPointer] == 'C') {
                 cCheck++;
             } else if (sArr[endPointer] == 'G') {
                 gCheck++;
             } else if (sArr[endPointer] == 'T') {
                 tCheck++;
             }
         }
        }
        System.out.println(answer);

    }
}