[백준/자바] 12891 DNA 비밀번호

[백준/자바] 12891 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| 보다 작거나 같음이 보장된다.

 

 

📣 출력

첫 번째 줄에 민호가 만들 수 있는 비밀번호의 종류의 수를 출력해라.

 

 

 

---

 

 

 

💎 문제분석하기

 

첫번째 input은 문자열이 주어지고 만들어야 하는 문자열의 길이 P는 S보다 작거나 같다. 

두번째 input은 DNA 문자열이 주어진다. 

세번째 input은 부분 문자열에 포함되어야 할 A, C, G, T의 개소이다. 예를 들어 2 0 1 1은 A = 최소 2개, C 0개, G 최소 1개, T 최소 1개를 의미한다. 

 

출력해야하는 것은 2번째 input을 사용해서 3번째 input으로 주어진 조건을 만족시킬수 있는 종류의 수이다. 

 

문제 해결을 위해서 각각의 개수를 별도로 판단해 조합하는 방식으로 접근할 수 있겠지만 시간 복잡도가 높아지므로 1,000,000의 크기를 감당하지 못한다. 

 

부분 문자열의 길이는 P로 제한되어 있기 때문에 슬라이딩 윈도우 개념으로 풀 수 있다. 

 

 

크기를 유지한 채 이동하면서 조건을 탐색한다. 

 

 

첫번째 예시를 살펴보면 

 

따라서 출력값은 0이 된다. 

 

이와 같은 방식으로 윈도우를 옆으로 옮겨가며 조건과 실제 보유 현황을 비교하면서 출력 가능 여부를 판단한다. 

 

 

 

 

📜 슈도코드 작성하기 

 

먼저 필요한 변수를 생각해보자. 

 

S : 입력받는 전체 문자열 크기

P : 부분 문자열 크기 

A : 비밀번호로 받는 문자열 => 배열로서 보유

checkArray : 조건으로 부여되는 비밀번호 개수를 설정하는 배열

myArray : 탐색하는 윈도우가 가진 비밀번호 개수를 설정하는 배열

checkEachDnaCharacter : A,C,G,T 개별 문자마다 조건을 충족하는지 판단을 가능하게 해줄 변수 

 

 

본 로직은 두 줄기로 작동한다. 

 

1) 첫번째 P를 숫자대로 형성하고 A, C, G, T를 계산하고 비교하여 count를 해주는 방식 = 첫번째 윈도우 생성

 

2) 윈도우를 옮겨가면서 A, C, G, T 를 계산하고 비교하여 count 해주는 방식 

 

먼저 카운트 해주는 방식을 구현한다. 

 

count의 조건은 A, C, G, T의 최소 개수보다 내 윈도우가 보유한 배열이 커야한다는 것이다. 

 

이때 최소값인 0 0 0 0의 경우 자동으로 +1이 되는 것을 계산해준다. 

 

그 다음 1번과 2번을 순서대로 진행한다. 

 

이때 별도의 함수인 add와 remove를 만들어 캐릭터를 하나씩 움직이는 기능을 구현한다. 

이 함수에서 처리가 character move가 일어나면서 자동으로 A, C, G, T의 카운트와 비교가 가능하도록 한다. 

 

만약 최소값을 만족한다면 모든 루프를 돌지 않아도 되므로 break을 선언하여 탈출하고 윈도우를 moving 시켜 다음 값을 판단한다. 

 

 

 

 

💡 코드 구현하기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] checkArray;
	static int[] myArray;
	static int checkEachDnaCharacter;

	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;

		checkArray = new int[4];
		myArray = new int[4];
		checkEachDnaCharacter = 0;		// 카운트는 add와 remove 함수에서 진행되도록 한다.

		A = bf.readLine().toCharArray();
		st = new StringTokenizer(bf.readLine());

		for (int i = 0; i < 4; i++) {
			checkArray[i] = Integer.parseInt(st.nextToken());
			if (checkArray[i] == 0)		// 모두가 0인 경우를 따지기 위함
				checkEachDnaCharacter++;
		}


		// 1번 로직 : 최초의 윈도우를 형성한다.
		for (int i = 0; i < P; i++) {
			Add(A[i]);
		}

		if (checkEachDnaCharacter == 4)		// 0 0 0 0 인 경우 검증 필요 없이 자동으로 +1이 된다
			Result++;


		// 2번 로직 : 반복문을 돌며 윈도우의 위치를 해체했다가 다시 생성한다 = 이동한다
		for (int i = P; i < S; i++) {
			int j = i - P;
			Add(A[i]);
			Remove(A[j]);
			if (checkEachDnaCharacter == 4)  // A C G T 모두 만족을 해야하므로 4인 경우 +가 된다
				Result++;
		}
		System.out.println(Result);
		bf.close();
	}

	private static void Add(char c) { //새로 들어온 문자를 처리해주는 함수
		switch (c) {
			case 'A':
				myArray[0]++;
				if (myArray[0] == checkArray[0])
					checkEachDnaCharacter++;
				break;
			case 'C':
				myArray[1]++;
				if (myArray[1] == checkArray[1])
					checkEachDnaCharacter++;
				break;
			case 'G':
				myArray[2]++;
				if (myArray[2] == checkArray[2])
					checkEachDnaCharacter++;
				break;
			case 'T':
				myArray[3]++;
				if (myArray[3] == checkArray[3])
					checkEachDnaCharacter++;
				break;
		}
	}

	private static void Remove(char c) { //제거되는  문자를 처리해주는 함수
		switch (c) {
			case 'A':
				if (myArray[0] == checkArray[0])
					checkEachDnaCharacter--;
				myArray[0]--;
				break;
			case 'C':
				if (myArray[1] == checkArray[1])
					checkEachDnaCharacter--;
				myArray[1]--;
				break;
			case 'G':
				if (myArray[2] == checkArray[2])
					checkEachDnaCharacter--;
				myArray[2]--;
				break;
			case 'T':
				if (myArray[3] == checkArray[3])
					checkEachDnaCharacter--;
				myArray[3]--;
				break;
		}
	}
}

 

 

 

 

 

 

 

 

 

---

 

 

 

풀이 참고 : Do it! 알고리즘 코딩테스트 - 자바 편