[백준] 12819번 DNA 비밀번호

✏️인프런 Do it! 알고리즘 코딩테스트 java 편을 듣고 푼 문제입니다. 

 

 

 

 

 

✍️풀이방식

 

슬라이딩 윈도우 알고리즘이란?

2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결한다 → 투 포인터 알고리즘과 비슷하고 원리도 간단

 

keypoint : 슬라이딩 윈도우 원리 이해 , 실제 문자열과 관련된 배열 처리 

 

 

 

슈도 코드 작성

//배열 저장 (s 배열 p 배열 저장 ) 
S(문자열 크기) P (부분 문자열의 크기) 
A( 문자열 데이터) 
CheckArr(비밀번호 체크 배열) 

//변수 선언 

myArr(현재 상태 배열) 
cheackSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수) 
P 범위(0~p-1)만큼 s 배열에 적용하기 , 유효한 비밀번호인지 판단
for(i를 P에서 5까지 반복)
{

}

 

---

 

🖥️문제풀이

 

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

public class Main
{
    static int myArr[]; //전역 변수로 선언 
    static int checkArr[]; 
    static int checkSecret; 
	public static void main(String[] args)throws IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 StringTokenizer st = new StringTokenizer(br.readLine()); //한줄 읽음 s, p 배열 
		 
		  int S = Integer.parseInt(st.nextToken()); // 문자열 크기 
		  int P = Integer.parseInt(st.nextToken()); // 부분 문자열 크기 
		  int Result = 0; 
		  checkArr = new int[4]; 
		  myArr = new int[4]; //현재 상태 배열 (a,c,g,t가 얼만큼 있는지 체크 ) 
		  char A[] = new char[S];
		  checkSecret = 0; // 몇개가 비밀번호를 만족하는지 체크 
		  //변수가 4가되면 정답 카운트 증가 
		  
		 
		 A = br.readLine().toCharArray();
		 st = new StringTokenizer(br.readLine());
		 for (int i=0;i<4;i++){
		     checkArr[i] = Integer.parseInt(st.nextToken()); //2 0 1 1 부분 문자열에 포함돼야 할 A C G T의 최소 개수
		     if(checkArr[i]==0){ // 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]);//새로 추가된 1개 체크 
		     Remove(A[j]);//기존 왼쪽 배열 제거 
		     if(checkSecret ==4)Result ++; 
		 }
		 
		 System.out.println(Result);
	     br.close();
		
		 
	}
	
	private static void Remove(char c){
		     switch(c){
	             case 'A': 
	                 if(myArr[0]==checkArr[0])checkSecret--; //A를 만족한다 
	                 myArr[0]--;
	                 break; 
	             case 'C':
	                 if(myArr[1]==checkArr[1])checkSecret--; //C를 만족한다 
	                 myArr[1]--;
	                 break;
	             case 'G':
	                 if(myArr[2]==checkArr[2])checkSecret--; //G를 만족한다 
	                 myArr[2]--;
	                 break;
	             case 'T':
	                 if(myArr[3]==checkArr[3])checkSecret--; //T를 만족한다 
	                 myArr[3]--;
	                 break;
	         }
	         
		     
		 }
		 
		 
	 private static void Add(char c){
	         switch(c){
	             case 'A': 
	                 myArr[0]++;
	                 if(myArr[0]==checkArr[0])checkSecret++; //A를 만족한다 
	                 break; 
	             case 'C':
	                 myArr[1]++;
	                 if(myArr[1]==checkArr[1])checkSecret++; //C를 만족한다 
	                 break; 
	             case 'G':
	                 myArr[2]++;
	                 if(myArr[2]==checkArr[2])checkSecret++; //G를 만족한다 
	                 break; 
	             case 'T':
	                 myArr[3]++;
	                 if(myArr[3]==checkArr[3])checkSecret++; //T를 만족한다 
	                 break; 
	         }
	         
	     }
}

 

 

 

☑️실행결과