백준 12891번 - DNA 비밀번호

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

12891번: DNA 비밀번호

 

 

 

 

 

부분문자열을 구하는 문제로 처음에는 for문을 중첩해서 구하는 방법을 생각했다. 하지만 시간초과가 났다. 입력되는 문자열의 길이가 최대 1,000,000(백만)이다. for문을 중첩해서 돌린다면 O(n^2) 약 1,000,000(백만) * 1,000,000(백만) = 억 단위가 넘어가서 1초 안에 풀지 못한다...

 

 

 

 

 

실패

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

public class Main {

	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());
	
		char[] S = br.readLine().toCharArray();
		
		st = new StringTokenizer(br.readLine(), " ");
		int a = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int g = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
	
		//구현
		int answer = 0;
		for(int i = 0; i <= s - p; i++) {
			int a_count = 0, c_count = 0, g_count = 0, t_count = 0;
			for(int j = 0; j < p; j++) {
				switch(S[i + j]) {
				case 'A':
					a_count++;
					break;
				case 'C':
					c_count++;
					break;
				case 'G':
					g_count++;
					break;
				case 'T':
					t_count++;
					break;
				}
			}
			
			if(a_count >= a && c_count >= c && g_count >= g && t_count >= t) {
				answer++;
			}
		}
	
		//출력
		System.out.println(answer);
	}

}

 

 

 

 

 

 

이중 for문을 쓰는 O(n^2)의 시간을 O(n)으로 줄일 수 있는 방법은 슬라이딩 윈도우이다.

2 ~ i+1까지의 합 = 1~i까지의 합 + (i + 1)번째 원소 - 1번째 원소 .. 이런식으로 갱신해나가면 된다.

 

로직은 이걸 참고를 했다.

https://hanyeop.tistory.com/356

[알고리즘] 투 포인터, 슬라이딩 윈도우 알고리즘 자바 구현 (백준 2003, 2559)

 

 

 

 

 

코드

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

public class Main {

	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());
	
		char[] S = br.readLine().toCharArray();
		
		st = new StringTokenizer(br.readLine(), " ");
		int a = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());
		int g = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
	
		//구현
		//각 구간 별로 체크
		int answer = 0;
		int a_count = 0, c_count = 0, g_count = 0, t_count = 0;
		
		for(int i = 0; i < s; i++) {
			switch(S[i]) { //새로운 문자 조건 갱신
			case 'A':
				a_count++;
				break;
			case 'C':
				c_count++;
				break;
			case 'G':
				g_count++;
				break;
			case 'T':
				t_count++;
				break;
			}
			
			if(i == p - 1) { //가장 처음 암호문 판단
				if(a_count >= a && c_count >= c && g_count >= g && t_count >= t) {
					answer++;
				}
			}
			
			if(i >= p) { //이전 문자 조건 갱신
				switch(S[i - p]) {
				case 'A':
					a_count--;
					break;
				case 'C':
					c_count--;
					break;
				case 'G':
					g_count--;
					break;
				case 'T':
					t_count--;
					break;
				}
				
				if(a_count >= a && c_count >= c && g_count >= g && t_count >= t) {
					answer++;
				}
			}
		}
	
		//출력
		System.out.println(answer);
	}

}

 

 

 

 

 

 

결과