[BOJ] 12891. DNA 비밀번호 Python, Java

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

12891번: DNA 비밀번호

 

 

1. 해결방법

이 문제는 초기 값을 매우 크게 주고 있으므로, 보자마자 for문으로 모두 탐색을 시도한다는 것은 시간초과로 이어질 수 있다.

핵심은 O(N) 안으로 시간복잡도를 해결하는 것이며, O(N) 안으로 해결하기 위해서는 투 포인터를 이용하여 윈도우 슬라이딩 기법으로 해결하면 된다.


### 윈도우 슬라이딩
( 슬라이딩 윈도우 알고리즘 간단 예제 )
1, 2, 3, 4, 5, 6, 7 로 이루어진 숫자 배열에서 A[i] + A[i+1] + A[i+2] 형식으로 연속적인 3개의 숫자의 합의 최댓값을 구한다고 가정해보면 아래 5가지의 경우의 수가 나온다.

[1, 2, 3], 4, 5, 6, 7
1, [2, 3, 4], 5, 6, 7
1, 2, [3, 4, 5], 6, 7
1, 2, 3, [4, 5, 6], 7
1, 2, 3, 4, [5, 6, 7]

다음으로 합을 계산하는 고정된 크기의 배열의 변화를 보면 [1,2,3] => [2,3,4] => [3,4,5] ... => [5,6,7]이다. 
그렇다면 어떻게 최소한의 계산으로 다음 배열의 합을 구할 수 있을까?

- 먼저 처음 배열 [1,2,3] 의 합을 구한다. == 6
- 다음 배열은 [2,3,4]는 [1,2,3] 배열에서 맨 앞 값이 빠지고, 그다음 값인 4가 들어온 모습이다. 따라서 합은 (6-1+4) == 9 이다.
- 이러한 규칙을 바탕으로 보면 다음 배열의 값은 전 배열에서 처음 원소를 빼고 다음에 들어올 원소를 더해주면 된다는 것을 알 수 있당!!

### 끝

위 처럼 투 포인트의 위치를 첫 부분과 끝 부분을 잡아서 동시에 이동시켜 주는 것이다.
이 때, 이동 시킨 위치에서 지나간 지점은 값을 빼주고, 새롭게 들어온 지점은 값을 더해주면서 문자를 만들 수 있는지 유효성 검사를 진행하면 된다.....

 

 

2. 정답코드 Python

import sys
input = sys.stdin.readline

S, P = map(int, input().split())

pwd = list(map(str, input().strip()))
a, c, g, t = map(int, input().split())

chk = [0] * 4
answer = 0
len_pwd = len(pwd)

for i in range(P):
    if pwd[i] == 'A':
        chk[0] += 1
    elif pwd[i] == 'C':
        chk[1] += 1
    elif pwd[i] == 'G':
        chk[2] += 1
    elif pwd[i] == 'T':
        chk[3] += 1

if chk[0] >= a and chk[1] >= c and chk[2] >= g and chk[3] >= t:
    answer += 1

start, end = 0, P - 1
while True:
    if end == len_pwd - 1:
        break

    if pwd[start] == 'A':
        chk[0] -= 1
    elif pwd[start] == 'C':
        chk[1] -= 1
    elif pwd[start] == 'G':
        chk[2] -= 1
    elif pwd[start] == 'T':
        chk[3] -= 1

    start += 1
    end += 1

    if pwd[end] == 'A':
        chk[0] += 1
    elif pwd[end] == 'C':
        chk[1] += 1
    elif pwd[end] == 'G':
        chk[2] += 1
    elif pwd[end] == 'T':
        chk[3] += 1

    if chk[0] >= a and chk[1] >= c and chk[2] >= g and chk[3] >= t:
        answer += 1


print(answer)

 

 

3. 정답코드 Java

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

public class Main {
    static int S, P;
    static char[] pwd;
    static int[] chk = new int[4];
    static int a, c, g, t;
    static int start, end, answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken());
        P = Integer.parseInt(st.nextToken());

        pwd = new char[S];
        String chars = br.readLine();
        for (int i = 0; i < S; i++) pwd[i] = chars.charAt(i);

        st = new StringTokenizer(br.readLine());
        a = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        g = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        for (int i = 0; i < P; i++) {
            if (pwd[i] == 'A') chk[0] += 1;
            else if (pwd[i] == 'C') chk[1] += 1;
            else if (pwd[i] == 'G') chk[2] += 1;
            else if (pwd[i] == 'T') chk[3] += 1;
        }

        if (chk[0] >= a && chk[1] >= c && chk[2] >= g && chk[3] >= t) answer += 1;

        start = 0;
        end = P - 1;
        while (true) {
            if (end == S - 1) break;

            if (pwd[start] == 'A') chk[0] -= 1;
            else if (pwd[start] == 'C') chk[1] -= 1;
            else if (pwd[start] == 'G') chk[2] -= 1;
            else if (pwd[start] == 'T') chk[3] -= 1;

            start += 1;
            end += 1;

            if (pwd[end] == 'A') chk[0] += 1;
            else if (pwd[end] == 'C') chk[1] += 1;
            else if (pwd[end] == 'G') chk[2] += 1;
            else if (pwd[end] == 'T') chk[3] += 1;

            if (chk[0] >= a && chk[1] >= c && chk[2] >= g && chk[3] >= t) answer += 1;
        }
        System.out.println(answer);

    }
}

 

 

 

 

 

 

 

 

 

 

[참고]

https://ji-musclecode.tistory.com/37