[백준] 12891번: DNA 비밀번호 - java

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

public class Main {

	static int s_len;
	static int p_len;
	static char[] str;
	static int[] checkArr = new int[4];
	static int[] myArr = new int[4];
	static int checkCnt = 0; // {‘A’, ‘C’, ‘G’, ‘T’} 중 최소 개수를 일치한 문자 개수 (0~4)
	static int answer = 0; // 만들 수 있는 비밀번호 개수

	public static void main(String[] args) throws IOException {

		// 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		s_len = Integer.parseInt(st.nextToken());
		p_len = Integer.parseInt(st.nextToken());
		str = br.readLine().toCharArray(); // DNA 문자열
		st = new StringTokenizer(br.readLine());

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

		for (int i = 0; i < p_len; i++) { // 첫 부분문자열 셋팅 (0~p_len-1) 까지
			if (str[i]=='A') myArr[0]++;
			if (str[i]=='C') myArr[1]++;
			if (str[i]=='G') myArr[2]++;
			if (str[i]=='T') myArr[3]++;
		}

		if (checkCounting())// {‘A’, ‘C’, ‘G’, ‘T’} 4개의 문자가 모두 최소개수를 만족했다면
			answer++; // 만들 수 있는 비밀번호 개수 증가
		
		int i = -1;
		/**
		 * 부분문자열 만들기 => 이전 부분문자열의 첫 문자는 제외하고, 끝에서 1문자를 더 추가한다.
		 */
		for (int j = p_len; j < s_len; j++) { // 부분문자열의 끝을 나타내는 위치
			i = j - p_len; // 이전 부분문자열의 시작을 나타내는 위치
			
			// 이전 부분문자열의 시작 문자 제외
			if (str[i]=='A') myArr[0]--;
			if (str[i]=='C') myArr[1]--;
			if (str[i]=='G') myArr[2]--;
			if (str[i]=='T') myArr[3]--;
			
			// 이전 부분문자열의 끝에서 1문자 추가
			if (str[j]=='A') myArr[0]++;
			if (str[j]=='C') myArr[1]++;
			if (str[j]=='G') myArr[2]++;
			if (str[j]=='T') myArr[3]++;
			
			if (checkCounting())// {‘A’, ‘C’, ‘G’, ‘T’} 4개의 문자가 모두 최소개수를 만족했다면
				answer++; // 만들 수 있는 비밀번호 개수 증가
		}

		System.out.println(answer);

	}

	public static boolean checkCounting() {
		for (int i = 0; i < 4; i++) {
			if (myArr[i] < checkArr[i])
				return false;
		}
		return true;
	}

}

1. DNA문자열에서 길이가 P인 부분문자열을 구하기
=> 길이가 (1 ≤ |P| ≤ |S| ≤ 1,000,000) 로 재귀를 이용해서 부분문자열을 만드는 것은 매우 시간이 많이 걸릴 것이다.
=> 따라서 시작 인덱스와 끝 인덱스를 옮기는 슬라이딩 윈도우를 사용한다.

2. 시작되는 부분문자열은 0~p-1 까지다. 첫 부분문자열을 세팅한 후, 각 문자 하나하나에 대해 {A,C,G,T}의 개수를 센다. (myArr[])

3. 만약 부분문자열의 A,C,G,T의 각 개수가 각 문자의 최소문자를 만족한다면?
=> 비밀번호의 개수 answer을 증가한다.

- checkCounting() : 현재 부분문자열의 각 문자가 최소 문자개수를 만족하는지 여부를 리턴

4. 시작과 끝 인덱스를 옮겨가며 부분문자열을 만든다. (슬라이딩 윈도우)

=> for문으로 p번 인덱스부터 전체문자열의끝-1 까지 돌면서 부분문자열의 끝 문자를 갱신한다.
=> 위의 그림에서 볼 수 있듯이 이전 부분문자열의 첫 문자인 7은 제외되고,
새로운 끝 문자 1이 추가되는 방식이다.
=> 이전 문자열의 시작 문자의 경우, myArr[]에서 1씩 제외하고, 새로 추가된 끝 문자의 경우 myArr 에 추가해준다.
=> 새로만들어진 부분문자열에 대해 각 문자가 최소문자개수를 만족한다면? , answer을 1 증가시킨다.