문제

입력

출력

예제

idea

처음 했던 생각은 2중 for문을 이용하여 한칸씩 옆으로 이동하면서 각 문자열을 확인해 조건에 맞으면 출력을 하도록 알고리즘을 구현하였다. 하지만 그건 복잡도가 O(n^2)가 나와 시간초과가 나왔다.

그래서 고민은 해보며 공부를 한 결과 처음과 마지막만 구하면 된다는 것을 알게되었다.
그래서 처음에 범위 만큼 문자의 수를 구한 후 for문을 이용해 이전 글자의 첫번째 문자를 제거하고 다음에 들어올 문자를 더해주는 방식으로 구현을 하였다.

정리

• 처음 범위만큼 문자의 수를 각각 더해줌
• 이전의 첫번째 글자를 지워주고 다음에 들어온 문자를 추가시켜줌
  조건에 맞다면 +1

Code

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

public class Main {
	public static void main(String[] args) throws Exception {

		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());
		st = new StringTokenizer(br.readLine());
		String pw=st.nextToken();
		char password[]= new char[S];
		for (int i = 0; i < S; i++) {
			password[i]=pw.charAt(i);
		}
		int A,C,G,T;
		
		st = new StringTokenizer(br.readLine());
		A=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		G=Integer.parseInt(st.nextToken());
		T=Integer.parseInt(st.nextToken());
		int answer=0;
		int A_2=0, C_2=0, G_2=0, T_2=0;
		
		for(int j=0;j<P;j++) {
			if (password[j]=='A')
				A_2++;
			else if(password[j]=='C')
				C_2++;
			else if(password[j]=='G')
				G_2++;
			else if(password[j]=='T')
				T_2++;			
		}
		if(A_2>=A && C_2>=C && G_2>=G && T_2 >= T) 
			answer++;
		for (int i = 1;i<=S-P; i++) {
			
			if (password[i-1]=='A')
				A_2--;
			else if(password[i-1]=='C')
				C_2--;
			else if(password[i-1]=='G')
				G_2--;
			else if(password[i-1]=='T')
				T_2--;
			
			if (password[i+P-1]=='A')
				A_2++;
			else if(password[i+P-1]=='C')
				C_2++;
			else if(password[i+P-1]=='G')
				G_2++;
			else if(password[i+P-1]=='T')
				T_2++;	
	
			if(A_2>=A && C_2>=C && G_2>=G && T_2 >= T) 
				answer++;
			
//			if(i+P==S)
//				break;
		}
		System.out.println(answer);
	}
}

결과