[문제풀이] B12891 DNA비밀번호

DNA비밀번호

---

  🪅 String의 내장메서드 toCharArray()를 이용할 수 있는가
  🪅 검사하는 길이가 일정하다는 조건을 통해 슬라이딩 윈도우를 생각해낼 수 있는가
  🪅 이전의 결과를 최대한 써먹는 슬라이딩 윈도우 기법을 구현할 수 있는가
  🪅 반복되는 동작을 메서드로 구현할 수 있는가

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

public class Main {
    static char[] window;
    static int[] cnt;
    static int[] arr = new int[4]; // A C G T
    static int result;
    public static void Add(char c) {
        switch(c) {
             case 'A':
                 arr[0]++;
                 break;
             case 'C':
                 arr[1]++;
                 break;
             case 'G':
                 arr[2]++;
                 break;
             case 'T':
                 arr[3]++;
        }
    }
    public static void Remove(char c) {
        switch(c) {
             case 'A':
                 arr[0]--;
                 break;
             case 'C':
                 arr[1]--;
                 break;
             case 'G':
                 arr[2]--;
                 break;
             case 'T':
                 arr[3]--;
        }
    }
    public static boolean checkValid() {
        for(int i = 0; i < 4; i++) {
            if(arr[i] < cnt[i]) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer token = new StringTokenizer(br.readLine(), " ");
        int S = Integer.parseInt(token.nextToken()); // 전체문자열 개수 S 9
        int P = Integer.parseInt(token.nextToken()); // 부분문자열 개수 P 8
        window = br.readLine().toCharArray();


        token = new StringTokenizer(br.readLine(), " ");

        cnt = new int[4]; // A C G T
        for(int i = 0; i < 4; i++) {
            cnt[i] = Integer.parseInt(token.nextToken());
        }

        // P개의 부분문자 초기화
        for(int i = 0; i < P; i++) { // 길이가 P인 window
            Add(window[i]);
        }
        if(checkValid()) result++;

        for(int i = P; i < S; i++) { // sliding 횟수
            int front = i-P;
            int rear = i;
            Remove(window[front]);
            Add(window[rear]);
            if(checkValid()) result++;
        }

        System.out.println(result);
    }
}

💡 문제 접근 과정
검사해야하는 문자열의 길이가 P로 일정하다.
때문에 한 칸씩 이동하면서 문제 조건을 검사하는 ' 슬라이딩 윈도우 '로 해결할 생각을 했다.
처음에는 일일이 길이가 P인 문자열을 만들어가면서 검사했었는데,
그럴 필요없이, 인덱스를 이용해 조건에 맞는 결과만을 체크해나가는 방식으로 해결하는 것이 낫겠다는 생각을 했다.
슬라이딩 윈도우 방식은 이전의 결과를 최대한 써먹는 방식으로 문제를 해결해나간다
(즉, 한 칸(?) 이동할 때마다 P-1칸은 겹치게 된다.)
=> 이전의 결과에 맨 앞의 결과를 빼고 새로 이동한 맨 뒤의 결과를 더해주는 식이다.

이러한 동작을 (S-P)번 하면 길이가 P인 윈도우로 전체 S를 끝까지 검사할 수 있다.
이 때, 반복행동을 단계별 메서드로 만들어 전체적인 흐름을 볼 수 있게 했다.