[BOJ] 12891 DNA 비밀번호

DNA 비밀번호

풀이

• {'A','C','G','T'} 가 부분문자열에 포함되어야 할 최소 갯수가 주어지고, 부분문자열의 길이도 주어진다.
• 슬라이딩 윈도우를 떠올리면 되는 이유는 "연속되는 부분 문자열" 이고 "부분문자열의 길이"가 주어졌기 때문이다. 문자열의 길이가 가변적이라면 투 포인터로 풀 수 있겠지?
• 나는 슬라이딩 윈도우로 풀었다. 부분 문자열의 길이가 8로 주어졌다면, 먼저 주어진 문자열에 대해서 substring(0,8) 로 부분문자열 구한 뒤, A,C,G,T 가 만족해야 하는 최소갯수를 만족하는지 확인한다.
• 만족하지 않았다면, 이제 윈도우를 슬라이딩 시키면 되는데, index를 다음으로 옮기면서 a,c,g,t 중 해당하는 문자의 갯수를 +1 해주고, 슬라이딩 시켰으니까, 이전의 맨 앞 문자는 빼주면 된다.

  🙆‍♀️ 정답 풀이

  import java.util.*;
  import java.io.*;
  public class Main {
      static int aCnt=0,cCnt=0,gCnt=0,tCnt=0;
      static int[] cnt;
      public static void main(String[] args) throws Exception{
          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();
          cnt = new int[4];
          st = new StringTokenizer(br.readLine());
          for(int i=0;i<4;i++){
              cnt[i] = Integer.parseInt(st.nextToken());
          }
          //맨처음 cnt 세기
          for(int i=0;i<P;i++){
              checkDNA(str.charAt(i),true);
          }
          //a,c,g,t
          int answer = 0;
          if(checkPwd()){
              answer++;
          }
          //슬라이딩 윈도우
          for(int k=P;k<str.length();k++){
              //str[k] 는 더하고,
              //str[k-P] 는 빼고
              checkDNA(str.charAt(k),true);
              checkDNA(str.charAt(k-P),false);
              if(checkPwd()){
                  answer++;
              }
          }
          System.out.println(answer);
      }
      private static boolean checkPwd(){
          if(aCnt>=cnt[0] && cCnt>=cnt[1] && gCnt>=cnt[2] && tCnt>=cnt[3]) return true;
          return false;
      }
      private static void checkDNA(char k, boolean next){
          if(k=='A'){
              if(next) aCnt++;
              else aCnt--;
          }else if(k=='C'){
              if(next) cCnt++;
              else cCnt--;
          }else if(k=='T'){
              if(next) tCnt++;
              else tCnt--;
          }else if(k=='G'){
              if(next) gCnt++;
              else gCnt--;
          }
      }
  }