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

접근 방법 🧐

조합을 사용한다거나 하나씩 만든다는 개념으로 코드를 짜기에는 시간제한을 넘길 것 같고, 너무 노동일 것 같았다.
그러니.. 어떻게 풀어야할지 감이 안잡혔다!!

알고리즘 분류를 보니, 슬라이딩 윈도우..? 난생 처음 보는 단어라 검색해봤다
문제를 기준으로 설명해보자면,

• 처음에 P길로 문자열을 초기화 하고 한 방향으로 한칸씩 이동하는거다.
  
  
• 이동할 때마다 처음 초기화해둔 문자열의 문자 수를 담아둔 currNum에 증감을한다.
  
  
• 중간중간에 checkNum으로 맞게 됐는지 확인한다.

내가 쓴 코드 ✍️

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

public class Main {
	
	static int[] check;
	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());
		
		String str = br.readLine();
		char[] pw = new char[S];
		int[] dnaNum = new int[4];
		int[] currNum = new int[4];
		check = new int[4];
		int result=0;
		
		for(int i=0;i<S;i++) { //몇 개 있는지 체크
			pw[i] = str.charAt(i);
			if(pw[i] == 'A') dnaNum[0]++;
			if(pw[i]=='C') dnaNum[1]++;
			if(pw[i]=='G') dnaNum[2]++;
			if(pw[i]=='T') dnaNum[3]++;
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<4;i++) {//최소로 들어가야하는 개수
			check[i] = Integer.parseInt(st.nextToken());
		}
		
		if(!checkNum(dnaNum)) {
			System.out.print(result);
			return;
		}
		
		for(int i=0;i<P;i++) { //슬라이딩하기 위한 초기화 과정
			if(pw[i] == 'A') currNum[0]++;
			if(pw[i]=='C') currNum[1]++;
			if(pw[i]=='G') currNum[2]++;
			if(pw[i]=='T') currNum[3]++;
		}
		if(checkNum(currNum)) result++;
		
		for(int j=P;j<S;j++) { //j는 뒷부분 인덱스
			int i=j-P; //i는 앞부분 인덱스
			
			if(pw[i]=='A') currNum[0]--;
			if(pw[i]=='C') currNum[1]--;
			if(pw[i]=='G') currNum[2]--;
			if(pw[i]=='T') currNum[3]--;
			
			if(pw[j]=='A') currNum[0]++;
			if(pw[j]=='C') currNum[1]++;
			if(pw[j]=='G') currNum[2]++;
			if(pw[j]=='T') currNum[3]++;
			
			if(checkNum(currNum)) result++;
		}
		
		System.out.print(result);
	}
	
	public static boolean checkNum(int[] num) {
		for(int i=0;i<4;i++) {
			if(num[i] < check[i])
				return false;
		}
		return true;
	}
}

느낀점 📖

이 문제는 잘 몰라서 구글링하면서 풀었다.
의문점은, 슬라이딩 윈도우로 한 칸 씩 이동하는데 나올 수 있는 문자 조합이 다 나올 수 있는건가...? 잘 모르겠다. 아직 개념이 부족한듯하다