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

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

12891번: DNA 비밀번호

 

문제)

 

 

 

풀이)

 

이 문제는 슬라이딩 윈도우를 생각하면 좋다.

 

슬라이딩 윈도우?!

 

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘.

 

배열이나 리스트에서 요소의 일정 범위의 값을 비교할 때 사용할 수 있다!

 

예를 들어, 다음과 같이 윈도우 크기가 3인 윈도우를 보자.

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

1

2

3

4

5

6

 

이때, 이동할 때마다 첫 번째 원소는 윈도우에서 나가고, 나중 원소가 하나씩 들어옴을 확인할 수 있다.

즉, DNA 개수를 매번 다 계산하지 않고, 윈도우를 옮길 때마다 하나씩 추가, 삭제하는 작업을 거치면 된다!

 

 

나는 check 배열에 입력으로 주어진 비밀번호가 될 수 있는 AGCT 최소 개수를 저장하고,

sub 배열은 DNA 에서 윈도우만큼 자른 DNA 일부를 나타냈다.

이때, 각 배열의 index 0, 1, 2, 3은 A,G,C,T와 각각 대응한다!

 

Add 함수로 윈도우가 움직일때마다 추가되는 염기를 더해주고,

Remove 함수로 없어지는 염기를 제거해주었다.

나머지 Check 함수는 비밀번호 조건에 맞는지 확인하는 역할의 함수다.

 

 

import java.util.Scanner;

public class Main_BJ_12891_DNA비밀번호 {
	public static int[] check;
	public static int[] sub;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int s = sc.nextInt();
		int p = sc.nextInt();
		String str = sc.next();
		char[] dna = str.toCharArray();
		check = new int[4];
		sub = new int[4];
		for(int i=0; i<4; i++) {	// ACGT
			check[i]=sc.nextInt();
		}
		
		int count=0;
		for(int i=0; i<p; i++) {	//초기 설정
			Add(dna[i]);
		}
		
		if(Check())
			count++;
		
		
		for(int i=p; i<s; i++) {	//다음부터 더하고 빼기 반복
			int j = i-p;
			Add(dna[i]);
			Remove(dna[j]);
			if(Check())
				count++;
		}
		
		
		System.out.println(count);
		sc.close();
		
	}//main

	private static void Add(char c) {
		switch(c) {
		case 'A':
			sub[0]+=1;
			break;
		case 'C':
			sub[1]+=1;
			break;
		case 'G':
			sub[2]+=1;
			break;
		case 'T':
			sub[3]+=1;
			break;
		}
		
	}

	private static void Remove(char c) {
		switch(c) {
		case 'A':
			sub[0]-=1;
			break;
		case 'C':
			sub[1]-=1;
			break;
		case 'G':
			sub[2]-=1;
			break;
		case 'T':
			sub[3]-=1;
			break;
		}
		
	}
	
	private static boolean Check() {
		if(check[0] > sub[0])
			return false;
		else if(check[1]>sub[1])
			return false;
		else if(check[2]>sub[2])
			return false;
		else if(check[3]>sub[3])
			return false;
		return true;
	}
	
}