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

문제 분석

P,S의 최대가 1,000,000으로 매우 크기때문에 O(N)의 시간 복잡도 알고리즘으로 문제를 해결해야한다.
부분 문자열의 길이가 P로 정해져있으므로 슬라이딩 윈도우를 사용하자.

슈도코드

S,P 입력받기
DNA 입력받기
int answer = 0;
int[] alpha = new int[26] //아스키코드 65~90
int[] checkCnt = new int[4]
for(0~P-1 반복) {
	alpha에 DNA의 문자 개수 하나씩 카운트
}
for(4번 반복) {
	checkCnt에 A,C,G,T 개수 입력받기
}
int index = 0;

while(P+index <= S의 사이즈) {
  if(alpha[0] >= checkCnt[0] && alpha[3] >= checkCnt[1] && alpha[7] >= checkCnt[2] && (alpha[20] >= checkCnt[3])) {
      answer++;
  }
  DNA에서 index에 해당하는 문자 alpha에서 -1
  index++
  DNA에서 P+index에 해당하는 문자 alpha에서 +1
}

제출 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		int answer = 0;
		int[] alpha = new int[26]; 
		int[] checkCnt = new int[4];
		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 dna = st.nextToken();
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<4; i++) {
			checkCnt[i] = Integer.parseInt(st.nextToken());
		}

		for(int i=0; i<p; i++) {
			int ascii = dna.charAt(i);
			int alphabet = ascii - 65;
			alpha[alphabet]++; 
		}
		int index = -1;
		while(p+index < dna.length()) {
		  index++;
		  if(alpha[0] >= checkCnt[0] && alpha[2] >= checkCnt[1] && alpha[6] >= checkCnt[2] && alpha[19] >= checkCnt[3]) {
		      answer++;
		  }
		  if(p+index < dna.length()) { // 인덱스 초과 에러 예방
			  int start = dna.charAt(index) -65;
			  alpha[start]--;
			  int end = dna.charAt(p+index) -65;
			  alpha[end]++;
		  }
		}
		System.out.println(answer);
	}
}

공부한 사항

• 문자열 크기 : length()
• 슬라이딩 윈도우 : 움직일 때, 제외되는 부분과 추가되는 부분을 업데이트하는것이 포인트!

주의할 점

• 슬라이딩 로직의 while블록에서 처음에 index++를 하니, while문을 빠져나오기 직전인 마지막 루프에서 dna의 인덱스 초과 에러가난다.
  결국 마지막에는 슬라이딩을 더 이상 하지않고, 비밀번호로 가능한지 체크만 하면되기때문에 인덱스 범위 초과 에러가 나지않기위해서는 슬라이딩 해주는 부분에 추가적인 조건문 체크가 필요하다.

• 비밀번호 조건에 만족하는지 확인하는 로직에서, 각 문자들을 아스키코드값으로 변환해 체크했는데, 이 때 숫자로 변환하는 과정에서 잘못된 숫자를 입력할 수 있으므로 주의!

---

다른 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
public class Main {
	static int checkArr[];
	static int myArr[];
	static int checkSecret;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int S = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		int Result = 0;
		
		char A[] = new char[S];
		checkArr = new int[4];
		myArr = new int[4];
		checkSecret = 0;
		A = bf.readLine().toCharArray();
		st = new StringTokenizer(bf.readLine());
		for(int i =0 ; i< 4; i++) {
			checkArr[i] = Integer.parseInt(st.nextToken());
			if(checkArr[i] == 0) checkSecret++;
		}
		
		for(int i =0 ;i <P; i++) {
			Add(A[i]);
		}
		if(checkSecret == 4) Result++;
		
		for( int i =P; i<S; i++) {
			int j = i-P;
			Add(A[i]);
			Remove(A[j]);
			if(checkSecret == 4) Result++;
		}
		System.out.println(Result);
		bf.close();
		
	}
	
	private static void Add(char c) {
		switch(c) {
		case 'A' :
			myArr[0]++;
			if(myArr[0] == checkArr[0]) checkSecret++;
			break;
		case 'C' :
			myArr[1]++;
			if(myArr[1] == checkArr[1]) checkSecret++;
			break;
		case 'G' :
			myArr[2]++;
			if(myArr[2] == checkArr[2]) checkSecret++;
			break;
		case 'T' :
			myArr[3]++;
			if(myArr[3] == checkArr[3]) checkSecret++;
			break;
		}
	}
	
	private static void Remove(char c) {
		switch(c) {
		case 'A' :
			if(myArr[0] == checkArr[0])
				checkSecret--;
			myArr[0]--;
			break;
		case 'C' :
			if(myArr[1] == checkArr[1])
				checkSecret--;
			myArr[1]--;
			break;
		case 'G' :
			if(myArr[2] == checkArr[2])
				checkSecret--;
			myArr[2]--;
			break;
		case 'T' :
			if(myArr[3] == checkArr[3])
				checkSecret--;
			myArr[3]--;
			break;
		}
	}
}

공부한 사항

• toCharArray() : 문자열을 한 글자씩 쪼개서 문자 배열에 넣어준다.
• switch - case 문 :

switch(입력변수) {
    case 입력값1: ...
         break;
    case 입력값2: ...
         break;
    ...
    default: ...
         break;
}