[알고리즘] 2-4. 슬라이딩 윈도우 # [+deque 데크 자료구조]

1. 슬라이딩 윈도우

: 2개의 포인터의 범위에서 범위를 유지한 채, 이동하면서 조건에 맞는 경우를 찾는 알고리즘

 

문제 09. DNA 비밀번호

평소 문자열을 이용해 노는 것을 좋아하는 민호는 DNA 문자열을 알게 됐다. DNA 문자열은 모든 문자열에 등장하는 문자가 {'A'，'C'，'G'，'T'}인 문자열을 말한다. 예를 들어 "ACKA"는 DNA 문자열이 아니지만，"ACCA"는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을만들고 만들어진 DNA 문자열의 부분 문자열을 비 밀번호로 사용하기로 마음먹었다. 하지만 민호는 이 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분 문자열을 뽑았을 때 "AAAA"와 같이 보안에 취약한 비밀번호가 만들어질 수 있기 때문이다. 그래서 민호는 부분 문자열에서 등장하는 문자의 개수가 특정 개수 이상이어야 비밀 번호로 사용할 수 있다는 규칙을 만들었다. 예를 들어 임의의 DNA 문자열이 "AAACCTGCCAA"이고，민호가 뽑을 부분 문자열의 길이를 4라고 가정해 보자. 그리고 부분 문자열에 'A'는 1 개 이상，'C'는 1 개 이상，'G■는 1 개 이상，T는 0개 이상 등장해야 비밀번호로 사용할 수 있다고 가정해 보자. 이때 "ACCT"는 'G'가 1 개 이상 등장해야 한다는 조건을만족하지 못해 비밀번호로 사용할 수 없지만, "GCCA"은 모든 조건을 만족하므로 비밀번호로 사용할 수 있다.

민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분 분자열의 길이 그리고 {'A'，'C', 'G'，'T'}가 각각 몇 번 이상 등장해야 비밀번호로 사용할 수 있는지, 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하시오. 단，부분 문자열이 등장하는 위치가 다르면 부분 문자열의 내용이 같더라도 다른 문자열로 취급한다.

입력
1 번째 줄에 민호가 임의로 만든 DNA 문자열의 길이 ISI와 비밀번호로 사용할 부분 문자열의 길이 |P|가 주어진다(1 <= IPI <= ISI <= 1,000,000). 2번째 줄에 민호가 임의로 만든 DNA 문자열이 주어진다. 3번째 줄에 부분 문자열에 포함돼 할 {'A', 'C', 'G', T}의 최소 개수가 공백 문자를 사이에 두고 각각 주어진다. 각각의 수는 데보다 작거나 같은 음이 아닌 정수로 총합은 데보다 작거나 같다는 것이 보장된다.

출력
좋은 수의 개수를 출력한다.

예제 입력 1 

9 8 // DNA 문자열의 길이，부분 문자열의 길이 0
CCTGGATTG //DNA 문자열
2 0 11 // 부분 문자열에 포함돼야 할 A, C, G, T의 최소 개수

 

예제 출력 1

0

예제 입력 2

4 2
GATA
1 0 0 1

 

예제 출력 2

2

---

1단계. 문제 분석하기

: P와 S의 길이가 1,000,000으로 매우 큼 -> O(n) 시간 복잡도 사용

-> 부분 문자열의 길이가 P임을 이용해 -> 슬라이딩 윈도우 사용 -> 배열 S의 길이만큼만 탐색을 한다.

 

2단계. 손으로 풀어 보기

1. S 배열과 비밀번호 체크 배열 저장
2. 윈도우에 포함된 문자로 현재 상태 배열을 만들고
   -> 현재 상태 배열과 비밀번호 체크 배열을 비교해 유효 비밀번호인지 판단
3. 윈도우를 한 칸씩 이동하며 현재 상태 배열을 변경 [제거 문자열과 신규 문자열만 변경]
   -> 변경한 현재 상태 배열을 비밀번호 체크 배열과 비교해 비밀번호 유효성 체크

3단계. 슈도코드 작성하기

// 데이터 저장
S（문자열 크기） P(부분 문자열의 크기）
A（문자열 데이터）
checkArr（비밀번호 체크 배열）

// 변수 선언
myArr（현재 상태 배열）
checkSecret（몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수）
P 범위（0 〜 P - 1）만큼 S 배열에 적용하고, 유효한 비밀번호인지 판단하기
for（i를 P에서 제지 반복）
{
	j 선언 （i - P）
	// 이 부분은 함수로 별도 구현하기
	한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열을 처리하기
	유효한 비밀번호인지（checkSecret == 4） 판단해 결괏값에 업데이트하기
}
결괏값 출력하기

별도 함수
Add（문자 더하기 함수）
{
	새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
}
Remove （문자 빼기 함수）
{
	제거되는 문자를 myArr에 업데이트하거나 checkSecret 값 변경하기
}

 

package datastructure.ch03;

import java.util.Scanner;

//ACGT
public class ds_q09 {
	public int solution(int n, int m, String str, int[] arr) {
		int answer=0;
		char [] arr2 = str.toCharArray();
		int[] output=new int[arr.length];
		
		for(int i=0;i<m;i++) {
			if(arr2[i]=='A') output[0]+=1;
			else if(arr2[i]=='C') output[1]+=1;
			else if(arr2[i]=='G') output[2]+=1;
			else if(arr2[i]=='T') output[3]+=1;
		}
		if(arr[0]<=output[0]) 
			if(arr[1]<=output[1])
				if(arr[2]<=output[2])
					if(arr[3]<=output[3])
						answer++;
		
		for(int i=1;i<=n-m;i++) {
			if(arr2[i+m-1]=='A') output[0]+=1;
			else if(arr2[i+m-1]=='C') output[1]+=1;
			else if(arr2[i+m-1]=='G') output[2]+=1;
			else if(arr2[i+m-1]=='T') output[3]+=1;
			
			if(arr2[i-1]=='A') output[0]-=1;
			else if(arr2[i-1]=='C') output[1]-=1;
			else if(arr2[i-1]=='G') output[2]-=1;
			else if(arr2[i-1]=='T') output[3]-=1;
			
			if(arr[0]<=output[0]) 
				if(arr[1]<=output[1])
					if(arr[2]<=output[2])
						if(arr[3]<=output[3])
							answer++;
		}
		
		
		return answer;
	}
	public static void main(String[] args) {
		ds_q09 T = new ds_q09();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int m=kb.nextInt();
		String str=kb.next();
		int [] arr = new int[4];
		for(int i=0;i<4;i++) arr[i]=kb.nextInt();
		System.out.println(T.solution(n,m,str,arr));
	}

}

 

+) 세련된 풀이

 

---

문제 10. 최솟값 찾기

N개의 수 A1, A2, AN과 L이 주어진다. Ai-L+1 〜 Ai 중 최솟값을 Di라고 할 때 D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때 i <= 0 인 Ai는 무시하고 D를 구해야 한다.

 

입력
1 번째 줄에 N과 L(1 <= L < N <= 5,000,000), 2번째 줄에 N개의 수 A가 주어진다(-109 <= Ai <= 109).
출력
1 번째 줄에 Di를 공백으로 구분해 순서대로 출력한다.

 

예제 입력 1

12 3 // 숫자의 개수，슬라이 딩 윈도우의 크기 
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 1

1 1 1 2 2 2 2 2 3 3 2 2

 

---

1단계. 문제 분석하기

->

 

2단계. 손으로 풀어 보기

->

 

3단계. 슈도코드 작성하기