백준 12891 DNA 비밀

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

12891번: DNA 비밀번호

 

---

배운 내용

 1. 스캐너로 문자열을 입력 받고 char 배열로 처리

	char [] arr = new char[S];
	arr = sc.next().toCharArray();

2. 접근 방식

   N의 수가 최대 1,000,000이므로 O(N)의 알고리즘으로 풀어야 한다. 한 번의 배열을 탐색할 때 TRUE여부를 체크해    야 하므로 새롭게 추가된 문자에 집중하여 기존의 것에서 추가, 삭제 해야한다. 그러므로 슬라이싱 방식을 이용한다.

또한 중요한 것은 주어진 입력 값이 'DNA 문자열'이라는 점이다. 그러므로 다른 문자가 문자열에 들어 있는지 체크할 필요 없이  'A', 'C', 'G', 'T'의 개수 여부에 초점을 두어 문제를 푼다.

 

 

전체 코드

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

public class Main {
	static int checkNum = 0;
	static int checkArr [] = new int[4];
	static int userArr [] = new int[4];
    public static void main(String [] args) throws IOException {
   
	Scanner sc = new Scanner(System.in);
	int S = sc.nextInt();
	int P = sc.nextInt();
	int count = 0;
	int num=0;
	
	char [] arr = new char[S];
	arr = sc.next().toCharArray();
	
	//4개의 문자 제한 조건을 배열에 넣어둠
	for(int i=0; i<4;i++) {
		checkArr[i] = sc.nextInt();
		if(checkArr[i] !=0 ) num++;
	}
		
	//처음 문자열 검사
	for(int i =0; i< P; i++) {
		Add( arr[i]);
	}
	if(checkNum ==num)count++;
	
    //i는 삭제해야 하는 문자를 가리키는 인덱스
	int i=0;
    //j는 추가해야 되는 문자를 가리키는 인덱스
	int j = i+P;
	while(j<S) { // j가 마지막 문자의 인덱스를 가리키면 그만
		//한 칸 전진
		Remove(arr[i]);
		Add(arr[j]);
		if(checkNum==num)count++;	
		i++;
		j++;
	}
	
	System.out.println(count);
   }
   

   static void Add ( char ch) {
	   switch (ch) {
	   case 'A':
		   userArr[0]++;
		   //요구제한을 충족했으면 checkNum +1
		   // 요구조건이 1개라면 1개가 될 때 +1 했으므로 2개,3개가 되어도 +1 할 필요가 없다
		   if(userArr[0] == checkArr[0])
			  checkNum++;		   
		   break;
	   case 'C':
		   userArr[1]++;
		   if(userArr[1] == checkArr[1])
				  checkNum++;	
		   break;
	   case 'G':
		   userArr[2]++;
		   if(userArr[2] == checkArr[2])
				  checkNum++;	
		   break;
	   case 'T':
		   userArr[3]++;
		   if(userArr[3] == checkArr[3])
				  checkNum++;	
		   break;
	   }
   }
   
   static void Remove (char ch) {
	   switch (ch) {
	   case 'A':
		   // 요구 조건보다 작아질 때 -1
		   if(userArr[0] == checkArr[0])
				  checkNum--;	
		   userArr[0]--;	   
		   break;
	   case 'C':
		   if(userArr[1] == checkArr[1])
				  checkNum--;	
		   userArr[1]--;
		   break;
	   case 'G':
		   if(userArr[2] == checkArr[2])
				  checkNum--;	
		   userArr[2]--;
		   break;
	   case 'T':
		   if(userArr[3] == checkArr[3])
				  checkNum--;	
		   userArr[3]--;
		   break;
		
	   }
   }
  
}