009. DNA 비밀번호(백준12891번)

문제

문제 분석하기

지문에서 알수있는 정보들

• A, C, G, T 의 문자들로만 이루어진 문자열 = DNA 문자열
• DNA 문자열의 부분문자열을 사용한다.
• 부분문자열에 등장하는 문자는 개수에 대한 규칙이 있다.
• DNA문자열 중 규칙에 통과하는 부분문자열의 개수를 구하자

그 외 정보들

• 시간제한 2초 = 약 2억번의 연산안에 해결해야한다.
• $N = 1,000,000$ 이며, 데이터가 크다... $O(n)$ 의 시간복잡도를 가진 알고리즘으로 접근하자
• 문자열중 부분문자열 -> 윈도우? -> 슬라이딩 윈도우?!

손으로 풀어보기

첫 번째 입력을 토큰으로 나누어
첫번째 : DNA문자열의 길이 $S$
두번째 : 부분문자열의 길이(=윈도우길이) $P$
위와같이 저장

두번째 입력 = DNA문자열 저장 -> char 배열

세번째 입력 = 규칙 (부분문자열에 포함되야 할 A, C, G, T의 최소개수) -> int 배열

DNA문자열 배열에서 부분문자열의 길이 만큼 영역을 잡고 DNA문자열의 끝까지 한 칸씩 이동하며 규칙 비교
== 현재 윈도우에서 0번 인덱스가 빠지고 A[P] 의 인덱스 값이 들어옴
-> 현재의 부분문자열의 규칙을 저장할 int 배열 필요
-> 현재의 규칙과 사용자 입력 규칙 비교 후 같으면 result++; 후 한칸이동, 다르면 한칸이동

슈도코드 작성하기

int S = DNA문자열 길이 // 첫번째 입력
int P = 부분문자열 길이 // 첫번째 입력
char[] A = DNA 문자열 배열 // 두번째 입력
int[] checkArr = 사용자 입력 규칙 // 세번째 입력

int[] currArr = 현재 윈도우의 규칙

int checkNum = 몇개의 문자 규칙을 충족했는지? (4 == result++;)
int result = 출력될 결과값

for(int i=0; i<P; i++) { // 초기 윈도우 로직
	add(A[i]);
}

if(checkNum == 4) result++; // 규칙이 같으면 결과값++;

for(int i=P; i<S; i++) { // 슬라이딩 윈도우
	j = i-p;
	
	add(A[i]);
	remove(A[j]);
}

add(N) {
	switch(N) {
		case 'A':
			currArr[0]++;
			if(currArr[0] == checkArr[0]) checkNum++;
			break;
		case 'C':
			currArr[1]++;
			if(currArr[1] == checkArr[1]) checkNum++;
			break;
		case 'G':
			currArr[2]++;
			if(currArr[2] == checkArr[2]) checkNum++;
			break;
		case 'T':
			currArr[3]++;
			if(currArr[3] == checkArr[3]) checkNum++;
			break;
	}
}

remove(N) {
	switch(N) {
		case 'A':
			if(currArr[0] == checkArr[0]) checkNum--;
			currArr[0]--;
			break;
		case 'C':
			if(currArr[1] == checkArr[1]) checkNum--;
			currArr[1]--;
			break;
		case 'G':
			if(currArr[2] == checkArr[2]) checkNum--;
			currArr[2]--;
			break;
		case 'T':
			if(currArr[3] == checkArr[3]) checkNum--;
			currArr[3]--;
			break;
	}
}

코드 구현하기

import java.io.BufferedReader;  
import java.io.BufferedWriter;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.io.OutputStreamWriter;  
import java.util.StringTokenizer;  
  
public class Main {  
  
    private static int[] currArr;  
    private static int[] checkArr;  
    private static int checkNum;  
  
    public static void main( String[] args ) throws IOException {  
       BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );  
       BufferedWriter bw = new BufferedWriter( new OutputStreamWriter( System.out ) );  
       StringTokenizer st = new StringTokenizer( br.readLine() );  
  
       int S = Integer.parseInt( st.nextToken() );  
       int P = Integer.parseInt( st.nextToken() );  
       int result = 0;  
  
       st = new StringTokenizer( br.readLine() );  
       char[] A = st.nextToken().toCharArray();  
  
       currArr = new int[4];  
       checkArr = new int[ 4 ];  
       st = new StringTokenizer( br.readLine() );  
       for ( int i = 0; i < 4; i++ ) {  
          checkArr[ i ] = Integer.parseInt( st.nextToken() );  
          if ( checkArr [i] == 0) checkNum++;  
       }  
  
       for ( int i = 0; i < P; i++ ) {  
          add( A[ i ] );  
       }  
  
       if(checkNum == 4)  
          result++;  
  
       for ( int i = P; i < S; i++ ) {  
          int j = i - P;  
          add( A[ i ] );  
          remove( A[ j ] );  
  
          if(checkNum == 4) result++;  
       }  
  
       bw.write( String.valueOf( result ) );  
  
       bw.flush();  
       bw.close();  
    }  
  
    private static void remove( char c ) {  
       switch(c) {  
          case 'A':  
             if(currArr[0] == checkArr[0]) checkNum--;  
             currArr[0]--;  
             break;  
          case 'C':  
             if(currArr[1] == checkArr[1]) checkNum--;  
             currArr[1]--;  
             break;  
          case 'G':  
             if(currArr[2] == checkArr[2]) checkNum--;  
             currArr[2]--;  
             break;  
          case 'T':  
             if(currArr[3] == checkArr[3]) checkNum--;  
             currArr[3]--;  
             break;  
       }  
    }  
  
    private static void add( char c ) {  
       switch (c) {  
          case 'A':  
             currArr[0]++;  
             if(currArr[0] == checkArr[0]) checkNum++;  
             break;  
          case 'C':  
             currArr[1]++;  
             if(currArr[1] == checkArr[1]) checkNum++;  
             break;  
          case 'G':  
             currArr[2]++;  
             if(currArr[2] == checkArr[2]) checkNum++;  
             break;  
          case 'T':  
             currArr[3]++;  
             if(currArr[3] == checkArr[3]) checkNum++;  
             break;  
       }  
    }  
  
} // end