🐣 백준 Q12891 - DNA 비밀번호 (java)

문제

---

• 백준 Q12891 - DNA 비밀번호

문자열이 주어지고
그 문자열의 부분문자열로 비밀번호를 만들것이다.

부분문자열을 구하는 문제이니 슬라이딩 윈도우 알고리즘을 이용해
2개의 포인터로 범위를 지정한 다음
범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결할것이다.

조건은 A, C, G, T의 최소 개수를 충족해야만 한다. 코드에서 문자 하나씩의 개수를 충족할 때마다 checkSecret의 개수를 1씩 증가시켜주고
checkSecret이 4가 되면 4개의 문자 모두 조건에 충족된 것으로
비밀 번호 종류의 수 하나가 완성된다. (Result++)

그렇게 구한 개수의 총합을 출력한다.

수도 코드

---

S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkArr(비밀번호 체크 배열)
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)

P 범위(0 ~ P - 1)만큼 S 배열에 적용하고, 유효한 비밀번호인지 판단하기
for(i를 P에서 S까지 반복)
{
  j 선언(i - P)
  // 이 부분은 함수로 별도 구현하기
  한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리하기
  유효한 비밀번호인지(checkSecret == 4) 판단해 결괏값에 업데이트하기
}
결괏값 출력하기

//별도 함수

Add(문자 더하기 함수)
{
  새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
}

Remove(문자 빼기 함수)
{
  제거되는 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
}

코드

---

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

public class Q12891_DNA비밀번호 {
	
  static int checkArr[]; // 비밀번호 체크 배열
  static int myArr[]; // 현재상태 배열
  static int checkSecret; // 몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수

  public static void main(String[] args) throws NumberFormatException, 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;
    char ArrS[];

    checkArr = new int[4]; // 비밀번호 체크 배열, 몇개의 알파벳이 필요한지
    myArr = new int[4]; // 현재상태 배열
    checkSecret = 0; // 몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수

    ArrS = br.readLine().toCharArray(); // (2번째 줄) ArrS[] = {C, C, T, G, G, A, T, T, G}
    st = new StringTokenizer(br.readLine()); //
    for (int i = 0; i < 4; i++) {
      checkArr[i] = Integer.parseInt(st.nextToken()); // (3번째 줄) checkArr[] = {2, 0, 1, 1}
      if (checkArr[i] == 0)
        checkSecret++; // 이미 조건에 충족했으니 1
    }
	
    for (int i = 0; i < P; i++) { // 초기 P 부분 문자열 처리 부분
      Add(ArrS[i]);
    }
	
    if (checkSecret == 4) // 카운트 만족 조건, 4개의 문자가 모두 조건에 만족 1+1+1+1
      Result++;
	
    // 슬라이딩 윈도우 처리 부분
    for (int i = P; i < S; i++) {
      int j = i - P;
      Add(ArrS[i]);
      Remove(ArrS[j]);
      if (checkSecret == 4) // 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;
    }
  }
  
/*
----- 예제 입력 1 -----
9 8
CCTGGATTG
2 0 1 1
----- 예제 출력 1 -----
0

----- 예제 입력 2 -----
4 2
GATA
1 0 0 1
----- 예제 출력 2 -----
2
 */
  
}