[12891번] DNA 비밀번호

 

📌 문제

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

12891번: DNA 비밀번호

 

📌 풀이

• 해당 문제는 슬라이딩 윈도우를 사용하여 풀이할 수 있습니다.
• 슬라이딩 알고리즘의 핵심은 마치 창문을 밀듯이 배열을 탐색하면서 이때 추가되는 배열 부분만을 검사하고 탐색범위가 밀리면서 앞 부분 배열값은 삭제하는 것입니다.
• 이를 통해 시간복잡도를 개선할 수 있습니다.

 

 

📌 코드

import java.io.*;
import java.util.*;


class Main {

  static int myArr[];
  static int checkArr[];
  static int checkSecret;
  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());
    int Result = 0; 
    checkArr = new int[4]; //비밀번호 체크배열 A,C,G,T 가 몇 개 이상이어야 하는지
    myArr = new int[4]; //현재 내 배열의 상태 A,C,G,T 개수
    char A[] = new char[S]; //주어지는 DNA 문자열
    checkSecret = 0; //현재 4개중에 몇개가 비밀번호 조건에 만족하는가

    A = br.readLine().toCharArray(); // DNA 문자열을 Array로 받음
    st = new StringTokenizer(br.readLine());          

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

      if(checkArr[i] == 0){
        checkSecret++; //0이면 0개이상인것을 의미하므로 모두 만족하여 ++
      }
    }

    for(int i = 0; i<P; i++){ //부분문자열을 처음 받을 떄 세팅 하는 부분 ['C','C','A','G']
      Add(A[i]);
    }

    if(checkSecret == 4) Result++;

    //슬라이딩 윈도우 적용
    for(int i = P; i < S; i++){
      int j = i - P;
      Add(A[i]); //추가로 들어가는 비밀번호 값만 넣어주면 된다.
      Remove(A[j]);
      if(checkSecret == 4) Result++;
    }
    System.out.println(Result);
    br.close();
  }

  private static void Add(char c){
    switch (c){
      case 'A':
        myArr[0]++;
        if(myArr[0] == checkArr[0]) checkSecret++;
        break;
      case 'C':
        myArr[1]++;
        if(myArr[1] == checkArr[1]) checkSecret++;
        break;
      case 'G':
        myArr[2]++;
        if(myArr[2] == checkArr[2]) checkSecret++;
        break;
      case 'T':
        myArr[3]++;
        if(myArr[3] == checkArr[3]) checkSecret++;
        break;
    }
  }  

    private static void Remove(char c){
    switch (c){
      case 'A':
        if(myArr[0] == checkArr[0]) checkSecret--;
        myArr[0]--;
        break;
      case 'C':
        if(myArr[1] == checkArr[1]) checkSecret--;
        myArr[1]--;
        break;
      case 'G':
        if(myArr[2] == checkArr[2]) checkSecret--;
        myArr[2]--;
        break;
      case 'T':
        if(myArr[3] == checkArr[3]) checkSecret--;
        myArr[3]--;
        break;
    }
  }  
}