[JAVA] 백준 12891 DNA 비밀번호 | 슬라이딩 윈도우

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

12891번: DNA 비밀번호

 

 

문제 해결 포인트

- 슬라이딩 윈도우 알고리즘을 이용하여 고정된 크기의 구간 결과를 계산

- 단순 반복문을 통해 매번 문자열의 특정 구간 발생한 문자 개수를 세면 시간 초과 발생

 

- P 길이만큼 각 문자의 발생 횟수를 카운트 하여 저장한다

- 0부터 N-P까지 한칸씩 이동하면서 해당 구간 앞 문자열은 제거, 가장 뒤 문자열 한칸 뒤 문자열은 추가하는 것을 반복

- 조건에 만족하는 비밀번호 발견시 answer 변수 ++

 

작성 코드

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

// mem : 22352KB
// time : 228ms

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 answer=0;
		int N = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		char[] dna = br.readLine().toCharArray();  //문자열을 문자 배열로 변환
		
		st = new StringTokenizer(br.readLine());
		int[] check = new int[4];  // 각 문자가 몇개 이상 발견 돼야하는지 저장 배열
		for (int i = 0; i < 4; i++) {
			check[i] = Integer.parseInt(st.nextToken());
		}
		
		// 첫 임시 비밀번호 알파벳 카운트
		int[] countAlph = new int[4];
		for (int j = 0; j < P; j++) {
			switch (dna[j]) {
			case 'A': countAlph[0]++; break;
			case 'C': countAlph[1]++; break;
			case 'G': countAlph[2]++; break;
			case 'T': countAlph[3]++; break;
			}
		}
		
		// 비밀번호 후보 
		for (int i = 0; i <= N-P; i++) {
			boolean flag = false;
			// 조건에 부합하는지 확인
			for(int j=0; j<4; j++) {
				if(countAlph[j] < check[j]) {
					flag = true;
					break;
				}
			}
			if (!flag) // 사용 가능한 비밀번호
				answer++;
			if(i==N-P) break;
			
			countAlph[position(dna[i])]--;  //맨 앞 문자 제거
			countAlph[position(dna[i+P])]++;  //뒤 문자 추가
		}
		
		System.out.println(answer);

	}
	
	// 각 문자의 위치를 확인 
	private static int position(char alph) {
		switch(alph) {
		case 'A' : return 0;
		case 'C' : return 1;
		case 'G' : return 2;
		case 'T' : return 3;
		}
		return -1;
	}

}

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

---

REFERENCE

https://ji-musclecode.tistory.com/37