백준 JAVA11 12891번 : DNA 비밀번호
Mention : 슬라이딩(Sliding) 윈도우(Window), 범위를 이동시켜서 탐색하자🪟➡️🪟
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’} 가 각각 몇번 이상 등장해야 비밀번호로 사용할 수 있는지 순서대로 주어졌을 때 민호가 만들 수 있는 비밀번호의 종류의 수를 구하는 프로그램을 작성하자. 단 부분문자열이 등장하는 위치가 다르다면 부분문자열이 같다고 하더라도 다른 문자열로 취급한다.
입력
| 첫 번째 줄에 민호가 임의로 만든 DNA 문자열 길이 | S | 와 비밀번호로 사용할 부분문자열의 길이 | P | 가 주어진다. (1 ≤ | P | ≤ | S | ≤ 1,000,000) |
두번 째 줄에는 민호가 임의로 만든 DNA 문자열이 주어진다.
| 세번 째 줄에는 부분문자열에 포함되어야 할 {‘A’, ‘C’, ‘G’, ‘T’} 의 최소 개수가 공백을 구분으로 주어진다. 각각의 수는 | S | 보다 작거나 같은 음이 아닌 정수이며 총 합은 | S | 보다 작거나 같음이 보장된다. |
출력
첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.
예제 입력 1
9 8
CCTGGATTG
2 0 1 1
예제 출력 1
0
예제 입력 2
4 2
GATA
1 0 0 1
예제 출력 2
2
슈도코드
S(임의로 만들 DNA 문자열의 길이)
P(비밀번호로 사용할 문자열의 길이) window
임의의 DNA 문자열을 입력받는다.
char[] DNA 문자열 생성
DNA 문자열 배열에 입력값을 넣어준다 (char로 따로따로 들어가야한다.)
A,C,G,T의 만족하는 카운트 생성
cnt(좋은 수 카운트)
시작인덱스 = 0
엔드인덱스 = P-1
while(endIndex가 DNA 문자열 배열 끝까지 가면 중단) {
A,C,G,T를 만족한다면 카운트를 입력받을 길이4의 dnaCnt배열을 생성한다.
for(window 범위만큼 반복) {
if(임의의 DNA배열[시작인덱스] == A,C,G,T) {
만족한다면, dnaCnt에 1을 더해준다;
}
}
if(dnaCnt 배열이 A,C,G,T의 만족하는 카운트 배열의 각 인덱스 값과 똑같다면)
{좋은수 카운트 ++}
시작인덱스 ++
엔드인덱스 ++ (슬라이드 윈도우)
}
출력 cnt
}
First Try
- 이중 for문으로 인해 시간초과인것으로 예측된다.
- 1,000,000 * 1,000,000… O(n^2)
package slidingWindow;
import java.util.Scanner;
public class P12891_dna {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int S = sc.nextInt();
int P = sc.nextInt();
String tempDna = sc.next();
char[] ctempDna = tempDna.toCharArray();
int[] fixNumber = new int[4];
for (int i = 0; i < 4; i++) {
fixNumber[i] = sc.nextInt();
}
int cnt = 0;
String dna = "ACGT";
char[] cDna = dna.toCharArray();
int startIndex = 0;
int endIndex = P-1;
while (endIndex != S) {
int[] dnaCnt = new int[4];
int j = 0;
for(int i = 0; i<P; i++) {
if(ctempDna[startIndex+j] == cDna[0]) {
dnaCnt[0] += 1;
} else if (ctempDna[startIndex+j] == cDna[1]) {
dnaCnt[1] += 1;
} else if (ctempDna[startIndex+j] == cDna[2]) {
dnaCnt[2] += 1;
} else if (ctempDna[startIndex+j] == cDna[3]) {
dnaCnt[3] += 1;
} j++;
}
if (fixNumber[0] == dnaCnt[0] && fixNumber[1] == dnaCnt[1] && fixNumber[2] == dnaCnt[2] && fixNumber[3] == dnaCnt[3]) {
cnt++;
}
startIndex++;
endIndex++;
}
System.out.println(cnt);
}
}
리팩토링 코드
- 슬라이딩 윈도우
- 범위(window) 가 이동할 때, 앞부분은 remove되고, 뒷부분에 add 되는 것이 시간복잡도를 낮추는 포인트이다.
package slidingWindow;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class P12891_dna {
static int checkArr[];
static int myArr[];
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());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
int cnt = 0;
char[] A = br.readLine().toCharArray();
checkArr = new int[4];
myArr = new int[4];
checkSecret = 0;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
checkArr[i] = Integer.parseInt(st.nextToken());
if (checkArr[i] == 0)
checkSecret++;
}
for (int i = 0; i < P; i++) {
Add(A[i]);
}
if (checkSecret == 4) {
cnt++;
}
//슬라이딩 윈도우
for (int i = P; i < S; i++) {
int j = i - P;
Add(A[i]);
Remove(A[j]);
if (checkSecret == 4)
cnt++;
}
System.out.println(cnt);
br.close();
}
private static void Add(char c) {
switch (c) {
case 'A':
myArr[0]++;
if (myArr[0] == checkArr[0])
checkSecret++;
break;
case 'C':
myArr[1]++;
if (myArr[1] == checkArr[1])
checkSecret++;
break;
case 'G':
myArr[2]++;
if (myArr[2] == checkArr[2])
checkSecret++;
break;
case 'T':
myArr[3]++;
if (myArr[3] == checkArr[3])
checkSecret++;
break;
}
}
private static void Remove(char c) {
switch (c) {
case 'A':
if (myArr[0] == checkArr[0])
checkSecret--;
myArr[0]--;
break;
case 'C':
if (myArr[1] == checkArr[1])
checkSecret--;
myArr[1]--;
break;
case 'G':
if (myArr[2] == checkArr[2])
checkSecret--;
myArr[2]--;
break;
case 'T':
if (myArr[3] == checkArr[3])
checkSecret--;
myArr[3]--;
break;
}
}
}
Leave a comment