슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 저장한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결한다.
투 포인터 알고리즘과 매우 비슷하다.
평소 문자열을 이용해 노는 것을 좋아하는 민호는 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개 이상 등장해야 한다는 조건을 만족하지 못해 비밀번호로 사용할 수 없지만, "GGCA"는 모든 조건을 만족하므로 비밀번호로 사용할 수 있다.
민호가 만든 임의의 DNA 문자열과 비밀번호로 사용할 부분 문자열의 길의 그리고 {'A', 'C', 'G', 'T'}가 각각 몇 번 이상 등장해야 비밀번호로 사용할 수 있는지, 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하시오. 단, 부분 문자열이 등장하는 위치가 다르면 부분 문자열의 내용이 같더라도 다른 문자열로 취급한다.
입력
1번째 줄에 민호가 임의로 만든 DNA 문자열의 길이 |S|와 비밀번호로 사용할 부분 문자열의 길이 |P|가 주어진다(1 ⪯ |P| ⪯ |S| ⪯ 1,000,000). 2번째 줄에 민호가 임의로 만든 DNA 문자열이 주어진다. 3번째 줄에 부분 문자열에 포함되여 할 {'A', 'C', 'G', 'T'}의 최소 개수가 공백 문자를 사이에 두고 각각 주어진다. 각각의 수는 |S|보다 작거나 같은 음이 아닌 정수로 총합 |S|보다 작거나 같다는 것이 보장된다.
출력
비밀 번호의 종류의 개수를 출력한다.
예제 입력
9 8 // DNA 문자열의 길이, 부분 문자열의 길이
CCTGGATTG
2 0 1 1
예제 출력
0
1단계 - 문제 분석하기
P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 이 때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우의 개념을 이용하면 문제를 쉽게 해결할 수 있다.
2단계 - 손으로 풀어 보기
1 S배열과 비밀번호 체크 배열을 저장한다.
2 윈도우에 포함된 문자로 현재 상태 배열을 만든다. 그런 다음 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효 비밀번호인지 판단한다.
3 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트한다. 현재 상태 배열을 업데이트 한 이후에는 비밀번호 체크 배열과 비교하여 비밀번호 유효성을 판단한다. 현재 상태 배열을 업데이트 할 때는 빠지는 문자열, 신규 문자열만 보고 업데이트 하는 방식으로 진행한다.
3단계 - sudo코드 작성하기
S(문자열 크기) P(부분 문자열의 크기)
A(문자열 데이터)
checkArr(비밀번호 체크 배열)
myArr(현재 상태 배열)
checkSecret(몇 개의 문자와 관련된 개수를 충족했는지 판단하는 변수)
P 범위(0 ~ P - 1)만큼 S 배열에 적용하고 유효한 비밀번호인지 판단하기;
for(i -> P ~ S) {
j 선언(i - P);
// 함수로 별도 구현
한 칸씩 이동하면서 제거되는 문자열과 새로 들어오는 문자열 처리;
유효한 비밀먼호인지(checkSecret == 4) 판단해 결괏값에 업데이트;
}
결괏값 출력;
// 별도 함수
Add(문자 더하기 함수) {
새로 들어온 문자를 myArr에 업데이트하거나 checkSecret 값 변경;
}
Remove(문자 빼기 함수) {
제거되는 문자를 myArr에 업데이트하거나 checkSecret 값 변경;
}4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Q9 {
static int checkArr[];
static int myArr[];
static int checkSecret;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
int Result = 0;
char A[] = new char[S];
checkArr = new int[4];
myArr = new int[4];
checkSecret = 0;
A = bf.readLine().toCharArray();
st = new StringTokenizer(bf.readLine());
for(int i = 0; i < 4; i++){
checkArr[i] = Integer.parseInt(st.nextToken());
if(checkArr[i] == 0)
checkSecret += 1;
}
for(int i = 0; i < P; i++){
Add(A[i]);
}
if(checkSecret == 4)
Result += 1;
for(int i = P; i < S; i++){
int j = i - P;
Add(A[i]);
Remove(A[j]);
if(checkSecret == 4)
Result += 1;
}
System.out.println(Result);
bf.close();
}
private static void Add(char c){
switch (c){
case 'A' :
myArr[0] += 1;
if(myArr[0] == checkArr[0])
checkSecret += 1;
break;
case 'C' :
myArr[1] += 1;
if(myArr[1] == checkArr[1])
checkSecret += 1;
break;
case 'G' :
myArr[2] += 1;
if(myArr[2] == checkArr[2])
checkSecret += 1;
break;
case 'T':
myArr[3] += 1;
if(myArr[3] == checkArr[3])
checkSecret += 1;
break;
}
}
private static void Remove(char c){
switch (c){
case 'A':
if(myArr[0] == checkArr[0])
checkSecret -= 1;
myArr[0] -= 1;
break;
case 'C' :
if(myArr[1] == checkArr[1])
checkSecret -= 1;
myArr[1] -= 1;
break;
case 'G' :
if(myArr[2] == checkArr[2])
checkSecret -= 1;
myArr[2] -= 1;
break;
case 'T' :
if(myArr[3] == checkArr[2])
checkSecret -= 1;
myArr[3] -= 1;
break;
}
}
}
- Do it! 알고리즘 코딩테스트 자바 편
