[백준] DNA 비밀번호(12891)

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

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

투 포인터 알고리즘과 매우 비슷하다.
(투 포인터 알고리즘 응용 버전 느낌)

문제를 보면 스토리텔링처럼 길게 쭉 써놨는데, 필자는 저런 문제를 싫어하는 편이다...
(차라리 수학 수식으로 된 기호가 더 낫겠다)

문제의 핵심은 특정 문자열과 부분 문자열의 길이, 그리고 {'A', 'C', 'G', 'T'}가 최소 몇 개 이상이 있어야 비밀번호로 사용할 수 있는지 주어졌을 때, 만들 수 있는 비밀번호 종류의 개수를 출력하는 것이다.

또한 데이터 크기가 최대 1,000,000으로 매우 크기 때문에 O(N)의 시간 복잡도 알고리즘으로 문제를 해결해야한다.

Python

따라서 파이썬 문제풀이 방법은 다음과 같다.

1. 범위가 P인 부분문자열에 담긴 문자 종류의 개수를 카운트하는 myList 생성

2. myadd 함수를 통해 길이 P만큼 문자를 하나씩 myList에 카운트

3. Secret 값이 4이면 A, C, G, T가 모두 만족했다는 의미이므로 answer 카운트

4. myadd 함수를 통해 가장 끝 부분에 문자 1개 추가, myremove 함수를 통해 가장 앞부분에 문재 1개를 제거한 다음,

   변경된 부분 문자열에서 조건을 만족하는 경우 answer 카운트하는 과정을 P부터 S까지 반복

※ myadd, myremove 함수와 Secret 값
myadd 함수에서 myList에 카운트된 특정 문자가 체크리스트에서 요구하는 개수와 같을 경우 Secret 값을 증가한다.

myremove 함수에서 myList에 카운트된 특정 문자가 체크리스트에서 요구하는 개수와 같을 경우 Secret 값을 감소한다.

정리하면 함수를 매번 실행할때마다 조건 검사를 통해 Secret 값을 증감시키므로 이 값이 4인 경우가 A, C, G, T의 최소 개수를 만족하는 상황이 된다.

import sys
input = sys.stdin.readline

# 'A'는 1개 이상, 'C'는 1개 이상 등 조건을 체크하는 체크리스트
checkList = [0] * 4

# 범위 P인 부분문자열에 담긴 문자 종류의 개수를 담는 나의 리스트
myList = [0] * 4

# 체크리스트와 나의 리스트를 myadd, myremove 함수에서 매번 비교하면서
# 개수가 같을 경우 더하거나 뺀다
checkSecret = 0

# 문자를 하나씩 추가하는 함수
def myadd(c):
    global checkList, myList, checkSecret
    if c == 'A':
        myList[0] += 1
        # 나의 리스트에 카운트한 문자 A가 체크리스트의 A의 개수와 조건이 맞을 경우
        if myList[0] == checkList[0]:
            checkSecret += 1 # Secret 값 증가

    elif c == 'C':
        myList[1] += 1
        # 나의 리스트에 카운트한 문자 C가 체크리스트의 C의 개수와 조건이 맞을 경우
        if myList[1] == checkList[1]:
            checkSecret += 1 # Secret 값 증가
    
    elif c == 'G':
        myList[2] += 1
        # 나의 리스트에 카운트한 문자 G가 체크리스트의 G의 개수와 조건이 맞을 경우
        if myList[2] == checkList[2]:
            checkSecret += 1 # Secret 값 증가
    
    elif c == 'T':
        myList[3] += 1
        # 나의 리스트에 카운트한 문자 T가 체크리스트의 T의 개수와 조건이 맞을 경우
        if myList[3] == checkList[3]:
            checkSecret += 1 # Secret 값 증가

# 문자를 하나씩 빼는 함수
def myremove(c):
    global checkList, myList, checkSecret
    if c == 'A':
        # 나의 리스트에 카운트한 문자 A가 체크리스트의 A의 개수와 조건이 맞을 경우
        if myList[0] == checkList[0]:
            checkSecret -= 1 # Secret 값 감소
        myList[0] -= 1
    
    elif c == 'C':
        # 나의 리스트에 카운트한 문자 C가 체크리스트의 C의 개수와 조건이 맞을 경우
        if myList[1] == checkList[1]:
            checkSecret -= 1 # Secret 값 감소
        myList[1] -= 1

    elif c == 'G':
        # 나의 리스트에 카운트한 문자 G가 체크리스트의 G의 개수와 조건이 맞을 경우
        if myList[2] == checkList[2]:
            checkSecret -= 1 # Secret 값 감소
        myList[2] -= 1

    elif c == 'T':
        # 나의 리스트에 카운트한 문자 T가 체크리스트의 T의 개수와 조건이 맞을 경우
        if myList[3] == checkList[3]:
            checkSecret -= 1 # Secret 값 감소
        myList[3] -= 1

answer = 0

S, P = map(int, input().split())
DNA = list(input())
checkList = list(map(int, input().split()))

# 값이 0이라는 것은 특정 문자열이 이미 조건을 만족하므로
for i in range(4):
    if checkList[i] == 0:
        checkSecret += 1 # Secret 값 증가

# 길이 P만큼 문자를 하나씩 나의 리스트에 카운트
for i in range(P):
    myadd(DNA[i])

# Secret 값이 4라는 것은 {'A', 'C', 'G', 'T'}가
# 최소 몇 개 이상어이야 하는 지에 대한 조건을 만족했다는 의미
if checkSecret == 4:
    answer += 1 # 정답 값 증가

# P부터 S까지 반복하면서
for i in range(P, S):
    # 가장 앞쪽부터 위치한 문자를 제거하기 위해 필요한 인덱스 j
    j = i - P

    # 가장 끝부분에 문자 1개 추가
    myadd(DNA[i])

    # 가장 앞부분에 문자 1개 제거
    myremove(DNA[j])

    # 변경된 부분 문자열에서 조건을 만족하는 경우
    if checkSecret == 4:
        answer += 1

print(answer)

Java

자바의 경우도 문제풀이 방법은 동일하다.

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

public class P_12891 {
    static int[] checkArr;
    static int[] myArr;
    static int checkSecret;

    public static void main(String[] args) throws NumberFormatException, 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());

        char[] arr = new char[S];
        st = new StringTokenizer(br.readLine());
        arr = st.nextToken().toCharArray();

        int Result = 0;
        checkArr = new int[4];
        myArr = new int[4];
        checkSecret = 0;

        // 값이 0이라는 것은 특정 문자열이 이미 조건을 만족하므로
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            checkArr[i] = Integer.parseInt(st.nextToken());
            if (checkArr[i] == 0)
                checkSecret++; // Secret 값 증가
        }

        // 부분문자열 길이 P만큼 하나씩 추가
        for (int i = 0; i < P; i++) {
            Add(arr[i]);
        }
        
        // Secret 값이 4라는 것은 A, C, G, T에 대한
        // 최소 조건을 모두 만족했다는 의미이므로
        if (checkSecret == 4)
            Result++;

        // P부터 S까지 반복하면서
        for (int i = P; i < S; i++) {
            // 가장 앞쪽에 위치한 문자를 제거하는 인덱스 j
            int j = i - P;
            
            // 가장 끝부분에 문자 1개 추가
            Add(arr[i]);
            
            // 가장 앞부분에 문자 1개 제거
            Remove(arr[j]);
            
            // 변경된 부분 문자열에서 조건을 만족하는 경우
            if (checkSecret == 4)
                Result++;
        }

        System.out.println(Result);
        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;
        }
    }
}