[백준 실버 2] 12891번: DNA 비밀번호

문제

https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

 

풀이

• 문자열에 ‘A’, ‘C’, ‘G’, ‘T' 만 등장하는 문자열을 DNA 문자열이라고 한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다.
• 길이 S의 임의의 DNA 문자열을 만들고, 이 DNA 문자열의 길이가 P인 부분문자열을 비밀번호로 사용하려고 한다.
• "AAAA" 같은 취약한 비밀번호가 만들어 질 수도 있기 때문에 문자의 개수가 일정 수 이상이 되는 부분문자열만 비밀번호로 채택한다.
• 예를 들어, “AAACCTGCCAA”에서 4자리의 부분문자열을 비밀번호로 사용하고 ‘A’ 는 1개 이상, ‘C’는 1개 이상, ‘G’는 1개 이상, ‘T’는 0개 이상이라는 조건을 단다면 “ACCT”는 조건에 불만족하므로 비밀번호로 사용할 수 없고, “GCCA”는 사용할 수 있다. 만들 수 있는 비밀번호의 종류의 수를 구해야 한다.
• 부분문자열이 만들어지는 위치가 다르다면 같은 내용의 부분문자열이라도 다르게 취급한다.
• S와 P의 크기는 최대 백만이다.

 

조건이 뭔가 많아 보이지만 길이가 P인 슬라이딩 윈도우를 다루는 문제라고 볼 수 있다.

슬라이딩 윈도우는 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다.

 

입력으로는 S와 P, 그리고 DNA 문자열과 부분문자열에 포함되어야 할 ‘A’, ‘C’, ‘G’, ‘T’ 의 최소 개수가 주어진다. 최소 개수로 주어지는 ‘A’, ‘C’, ‘G’, ‘T’ 를 크기가 4인 정수형 배열에 담아 각각 순서대로 0부터 3까지의 인덱스를 활용하여 사용하기로 하였다.

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());
String inputStr = br.readLine();

checkArr = new int[4];	// static으로 선언
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
    checkArr[i] = Integer.parseInt(st.nextToken());
}

 

처음에는 substring을 사용해 부분문자열을 만들어 준 뒤, 부분문자열을 처음부터 탐색하며 최소 개수를 만족하는지 체크하는 방식으로 문제를 풀었다.

하지만 이 방법은 한칸씩 이동하는 슬라이딩 윈도우에서 부분문자열의 처음과 끝을 제외한 나머지 부분은 중복된채로 계산되어 비효율적이라는 사실을 깨달았다.

// 대충 이런 식으로 풀었지만 바로 시간초과
for (int i = 0; i <= S - P; i++) {
    String subStr = inputStr.substring(i, i + P);

    for (int j = 0; j < P; j++) {
        char c = subStr.charAt(j);
		...
        }
    }
}

 

그래서 슬라이딩 윈도우의 맨 처음이 i 라고 할 때, i - 1 위치의 문자와 i + P - 1 위치의 문자만 반복해서 판단해주면 된다고 생각하였다.

이 방법으로 풀기 위해서는 맨 처음 인덱스가 0부터 시작하는 초기 부분문자열을 기준으로 만들어진 초기값 배열이 필요하였다.

int cnt = 0;
int subArr[] = new int[4];

String firstStr = inputStr.substring(0, P);
for (int k = 0; k < P; k++) {
    char c = firstStr.charAt(k);
    subArr[findIndex(c)]++;
}

 

이때 findIndex()는 부분문자열의 한 문자가 배열의 어떤 인덱스에 해당하는지 판별하기 위해 정의한 메서드이다.

private static int findIndex(char c) {
    int ans = 0;
    switch (c) {
    case 'A':
        ans = 0;
        break;
    case 'C':
        ans = 1;
        break;
    case 'G':
        ans = 2;
        break;
    case 'T':
        ans = 3;
        break;
    }

    return ans;
}

 

이렇게 subArr를 checkArr와 비교하여 조건을 만족하는지 판단해야 한다. checkDNA() 메서드를 정의하여 비교하는 과정을 만들었다.

private static boolean checkDNA(int[] arr) {
    if (arr[0] < checkArr[0] || arr[1] < checkArr[1] || arr[2] < checkArr[2] || arr[3] < checkArr[3]) {
        return false;
    }

    return true;
}

 

초기 부분문자열으로 subArr를 만들었다면 이 다음은 슬라이딩 윈도우를 사용해 길이 P의 부분문자열을 반복하여 검사하는 과정이 필요하다. 새로운 부분문자열을 모두 검사할 필요는 없고 이전의 부분문자열과 비교하였을 때 달리진 부분만 판단하면 된다. 즉, 이전 부분문자열의 맨 끝 인덱스와 새로운 부분문자열의 맨 끝 인덱스만 검사하면 된다.

두 부분에 만족하는 인덱스는 현재 인덱스 (슬라이딩 윈도우가 시작하는 인덱스) i 를 기준으로 i - 1과 i + P -1이다.

for (int i = 1; i <= S - P; i++) {
    char outChar = inputStr.charAt(i - 1);
    char inChar = inputStr.charAt(i + P - 1);

    subArr[findIndex(outChar)]--;
    subArr[findIndex(inChar)]++;

    if (checkDNA(subArr)) {
        cnt++;
    }
}

 

전체 코드 (Java)

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

public class Main {

	static int checkArr[];

	public static void main(String[] args) throws Exception {
		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());
		String inputStr = br.readLine();

		checkArr = new int[4];
		int subArr[] = new int[4];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			checkArr[i] = Integer.parseInt(st.nextToken());
		}

		int cnt = 0;

		String firstStr = inputStr.substring(0, P);
		for (int k = 0; k < P; k++) {
			char c = firstStr.charAt(k);
			subArr[findIndex(c)]++;
		}

		if (checkDNA(subArr)) {
			cnt++;
		}

		for (int i = 1; i <= S - P; i++) {
			char outChar = inputStr.charAt(i - 1);
			char inChar = inputStr.charAt(i + P - 1);

			subArr[findIndex(outChar)]--;
			subArr[findIndex(inChar)]++;

			if (checkDNA(subArr)) {
				cnt++;
			}
		}

		System.out.println(cnt);

	}

	private static int findIndex(char c) {
		int ans = 0;
		switch (c) {
		case 'A':
			ans = 0;
			break;
		case 'C':
			ans = 1;
			break;
		case 'G':
			ans = 2;
			break;
		case 'T':
			ans = 3;
			break;
		}

		return ans;
	}

	private static boolean checkDNA(int[] arr) {
		if (arr[0] < checkArr[0] || arr[1] < checkArr[1] || arr[2] < checkArr[2] || arr[3] < checkArr[3]) {
			return false;
		}

		return true;
	}
}

 

 

후기

문제를 풀기 전에 시간 초과를 염두하여 설계하는 습관을 들여야 한다는 생각이 들었다.