백준 12891 DNA 비밀번호 (JAVA 자바 풀이)
문제
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 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| 보다 작거나 같음이 보장된다.
출력
첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.
💡 풀이 과정
가능한 경우의 수를 모두 구하면 답은 구할 수 있지만 시간 초과를 받는다.
예를 들어 S - P 만큼의 반복문을 돌면서
P 만큼의 문자열을 각각 검증해주는 아래와 같은 코드는
주어지는 S와 P의 값에 따라 최대 1,000,000 제곱이 된다.
for (int i = 0; i <= alphabetCounts - partLength; i++) {
satisfyCondition(...)
}
private static boolean satisfyCondition(String string, int [] alphabetCondition){
char[] chars = string.toCharArray();
int[] charCounts = new int[4];
for (char aChar : chars) {
if (aChar == 'A') {
charCounts[0] ++;
}
if (aChar == 'C') {
charCounts[1] ++;
}
if (aChar == 'G') {
charCounts[2] ++;
}
if (aChar == 'T') {
charCounts[3] ++;
}
}
for (int i = 0; i< 4; i++){
if (charCounts[i] < alphabetCondition[i]){
return false;
}
}
return true;
}
투포인터를 응용한 기법인 슬라이딩 윈도우를 사용해서 문제를 풀어보자.
투포인터로 시작과 끝을 정한 특정 문자열에 대해서 포인터를 함께 이동해 가는 것이다.
이때 생각해볼 수 있는 점은 탐색을 할 때마다 공통되는 부분이 있다는 점이다.
예를 들어,
A C G ... G C C T ... 같이 문자열이 진행될 때
슬라이딩 윈도우 1 -> A C G ... G
에서
슬라이딩 윈도우 2 -> C G ... G C
로 이동했다고 하면
< C G ... G > 부분이 겹치는 것을 볼 수 있다.
이때 이전의 A 부분이 빠지고 C 부분이 추가된다.
이렇게 윈도우를 이동해가면서 이전에 사용했던 문자열을 재사용하여 카운팅 한다면, 즉 이전 부분문자열을 통해 다음 부분 문자열을 구할 때 시간 복잡도가 O(1)이므로 시간 복잡도를 개선할 수 있다.
알고리즘을 구현해보자.
먼저 첫 부분 문자열을 구한다. 슬라이딩 윈도우은 이전 슬라이드가 있어야 부분 문자열을 구할 수 있기 때문에 처음 초기값, 즉 처음 슬라이드를 먼저 만들어주고 가야 한다.
/**
* 슬라이딩 윈도우의 초기 설정을 한다.
* 주어진 DNA 문자열의 처음 partLength 길이만큼의 부분 문자열에 대해
* 각 문자('A', 'C', 'G', 'T')의 출현 횟수를 charCounts 배열에 저장한다.
* 즉, 슬라이딩 윈도우의 첫 상태를 설정한다.
*/
int[] charCounts = new int[4];
for (int i = 0; i < partLength; i++) {
charCounts[charToIndex(dnaString.charAt(i))]++;
}
이때 계산을 효율적으로 하기 위해 생성한 charToIndex 함수는 다음과 같다.
/**
* DNA 문자열의 각 문자를 해당하는 인덱스 값으로 변환한다.
* 예를 들어, 'A'는 0, 'C'는 1, 'G'는 2, 'T'는 3으로 변환된다.
* 이 함수는 문자열의 각 문자를 charCounts 배열의 적절한 위치에 매핑하는 데 사용된다.
* 문제의 조건에 따라 잘못된 알파벳이 입력될 수는 없다.
*/
private static int charToIndex(char c) {
switch (c) {
case 'A':
return 0;
case 'C':
return 1;
case 'G':
return 2;
case 'T':
return 3;
default:
throw new IllegalArgumentException("Invalid character: " + c);
}
}
문자열은 A, C, G, T 만 존재하는 것이 문제의 조건에 의해 보장되므로 해당 문자열인 경우 숫자로 바꾸어 카운트 배열을 만들어준다. 이렇게 하면
[_, _, _, _] 배열에 각각 A, C, G, T의 카운트가 세어지게 될 것이다.
첫 부분 문자열의 슬라이딩 윈도우 역시 답에 포함될 수 있기 때문에 해당 슬라이딩 윈도우를 검사한다.
/**
* 초기 슬라이딩 윈도우가 조건을 만족하는지 확인한다.
* satisfyCondition 함수를 사용하여 초기 윈도우가 각 문자에 대한 최소 출현 횟수 조건을 충족하는지 검사한다.
* 만약 충족한다면, 가능한 부분 문자열의 수(answer)를 1 증가시킨다.
*/
int answer = 0;
if (satisfyCondition(charCounts, alphabetCondition)) {
answer++;
}
검사하는 함수는 간단하게 위에서 만든 카운트 배열과 문제에서 제기된 조건 배열을 비교해주면 된다.
/**
* 주어진 윈도우가 모든 조건을 충족하는지 검사한다.
* 각 문자('A', 'C', 'G', 'T')에 대해 charCounts 배열에 저장된 출현 횟수가
* alphabetCondition 배열에 지정된 최소 출현 횟수 이상인지 확인한다.
* <p>
* 모든 조건을 충족하면 true를, 그렇지 않으면 false를 반환한다.
*/
private static boolean satisfyCondition(int[] charCounts, int[] alphabetCondition) {
for (int i = 0; i < 4; i++) {
if (charCounts[i] < alphabetCondition[i]) {
return false;
}
}
return true;
}
이제 슬라이딩 윈도우가 이동하는 프로세스를 구현해보자.
첫 번째 슬라이딩 윈도우를 위에서 만들었기 때문에 i는 1부터 시작한다. 슬라이딩 윈도우가 동일한 크기가 되도록 end 값을 지정해주고 반복문을 돌면서 각각의 회차에서 이전 요소를 빼어 카운팅, 새롭게 추가되는 요소를 추가하여 카운팅한다. 즉 카운팅 배열을 업데이트한다.
이때 업데이트 된 카운트 배열을 검증 함수를 통해 검증하고, 만약 검증에 통과한다면 답을 증가시켜준다.
/**
* 슬라이딩 윈도우를 DNA 문자열을 따라 한 칸씩 이동시키면서
* 각 윈도우가 조건을 만족하는지 확인한다.
*
* 윈도우가 이동할 때마다 윈도우의 시작 부분 문자는 제거하고, 새로운 끝 부분 문자를 추가한다.
*
* 각 이동 후에, satisfyCondition 함수를 사용하여 새로운 윈도우가 조건을 충족하는지 검사하고,
* 조건을 만족하면 answer를 증가시킨다.
*/
for (int start = 1; start <= alphabetCounts - partLength; start++) {
int end = start + partLength - 1;
charCounts[charToIndex(dnaString.charAt(start - 1))]--;
charCounts[charToIndex(dnaString.charAt(end))]++;
if (satisfyCondition(charCounts, alphabetCondition)) {
answer++;
}
}
전체 코드 구현은 아래와 같다.
💡 코드 구현
import static java.lang.Integer.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
return new StringTokenizer(bufferedReader.readLine());
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));
StringTokenizer stringTokenizer = receiveInput(bufferedReader);
int alphabetCounts = parseInt(stringTokenizer.nextToken());
int partLength = parseInt(stringTokenizer.nextToken());
String dnaString = receiveInput(bufferedReader).nextToken();
stringTokenizer = receiveInput(bufferedReader);
int[] alphabetCondition = new int[4];
for (int i = 0; i < 4; i++) {
alphabetCondition[i] = parseInt(stringTokenizer.nextToken());
}
/**
* 슬라이딩 윈도우의 초기 설정을 한다.
* 주어진 DNA 문자열의 처음 partLength 길이만큼의 부분 문자열에 대해
* 각 문자('A', 'C', 'G', 'T')의 출현 횟수를 charCounts 배열에 저장한다.
* 즉, 슬라이딩 윈도우의 첫 상태를 설정한다.
*/
int[] charCounts = new int[4];
for (int i = 0; i < partLength; i++) {
charCounts[charToIndex(dnaString.charAt(i))]++;
}
/**
* 초기 슬라이딩 윈도우가 조건을 만족하는지 확인한다.
* satisfyCondition 함수를 사용하여 초기 윈도우가 각 문자에 대한 최소 출현 횟수 조건을 충족하는지 검사한다.
* 만약 충족한다면, 가능한 부분 문자열의 수(answer)를 1 증가시킨다.
*/
int answer = 0;
if (satisfyCondition(charCounts, alphabetCondition)) {
answer++;
}
/**
* 슬라이딩 윈도우를 DNA 문자열을 따라 한 칸씩 이동시키면서
* 각 윈도우가 조건을 만족하는지 확인한다.
*
* 윈도우가 이동할 때마다 윈도우의 시작 부분 문자는 제거하고, 새로운 끝 부분 문자를 추가한다.
*
* 각 이동 후에, satisfyCondition 함수를 사용하여 새로운 윈도우가 조건을 충족하는지 검사하고,
* 조건을 만족하면 answer를 증가시킨다.
*/
for (int start = 1; start <= alphabetCounts - partLength; start++) {
int end = start + partLength - 1;
charCounts[charToIndex(dnaString.charAt(start - 1))]--;
charCounts[charToIndex(dnaString.charAt(end))]++;
if (satisfyCondition(charCounts, alphabetCondition)) {
answer++;
}
}
System.out.println(answer);
}
/**
* 주어진 윈도우가 모든 조건을 충족하는지 검사한다.
* 각 문자('A', 'C', 'G', 'T')에 대해 charCounts 배열에 저장된 출현 횟수가
* alphabetCondition 배열에 지정된 최소 출현 횟수 이상인지 확인한다.
* <p>
* 모든 조건을 충족하면 true를, 그렇지 않으면 false를 반환한다.
*/
private static boolean satisfyCondition(int[] charCounts, int[] alphabetCondition) {
for (int i = 0; i < 4; i++) {
if (charCounts[i] < alphabetCondition[i]) {
return false;
}
}
return true;
}
/**
* DNA 문자열의 각 문자를 해당하는 인덱스 값으로 변환한다.
* 예를 들어, 'A'는 0, 'C'는 1, 'G'는 2, 'T'는 3으로 변환된다.
* 이 함수는 문자열의 각 문자를 charCounts 배열의 적절한 위치에 매핑하는 데 사용된다.
* 문제의 조건에 따라 잘못된 알파벳이 입력될 수는 없다.
*/
private static int charToIndex(char c) {
switch (c) {
case 'A':
return 0;
case 'C':
return 1;
case 'G':
return 2;
case 'T':
return 3;
default:
throw new IllegalArgumentException("Invalid character: " + c);
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 1406 에디터 (JAVA 자바 풀이) (0) | 2023.12.28 |
|---|---|
| 백준 1158 요세푸스 문제 (JAVA 자바 풀이) (0) | 2023.12.28 |
| 백준 1806 부분합 (JAVA 자바 풀이) (1) | 2023.12.27 |
| 백준 2110 용돈 관리 (JAVA 자바 풀이) (1) | 2023.12.26 |
| 백준 6236 용돈 관리 (JAVA 자바 풀이) (0) | 2023.12.25 |
