백준 문제풀이 : (12891) DNA 비밀번호 - C/C++

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

12891번: DNA 비밀번호

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	512 MB	Silver 2	문자열, 슬라이딩 윈도우

 

 

문제

 

 

풀이

슬라이딩 윈도우란 '두 포인트' 알고리즘응 응용한 알고리즘으로, 두 포인터 사이의 구간을 지정하고 해당 구간을 n칸씩 옮겨가며 문제를 해결하는 방식이다.

 

어떤 조건을 만족하는 연속된 구간의 개수를 구할 때  유용하게 사용할 수 있으며, 두 포인터와 마찬가지로 실행횟수가 N번이므로 아주 경제적이다.

 

 문제에서는 길이가 S인 특정 문자열이 주어졌을 때, 그 속에서 조건을 만족하는 길이 P의 문자열을 몇 개 만들 수 있는 지 물어보고 있다. 즉, 길이 P의 문자열이 되는 조건은 아래와 같다.

 

1) 길이 P의 문자열의 구성원은 길이 S의 문자열의 연속된 값이다.

2) 길이 P의 문자열은 조건 'ACGT'을 만족한다.

 

여기서 조건 ACGT란 문자 A,C,G,T가 입력에서 주어진 횟수 대로 문자열 내에 포함되어있는 지를 뜻한다. 

 

풀이법은 슬라이딩 윈도우 알고리즘을 그대로 대입해, 다음의 순서대로 진행하면 된다.

 

1) 첫 번째 포인터(start)와 두 번째 포인터(end)의 처음 주소를 0번지로 지정한다.

2) end의 주소를 p-1번지 까지 1씩 증가시킨다.

2-1) 2를 반복하는 과정에서, end가 지나는 주소의 문자가 A, C, B, T 중 하나라면 해당 문자의 개수를 1 증가한다.

3) 2까지 진행했을 경우, start는 0번지에, end는 p-1번지 혹은 p번지에 있을 것이다. (for문 사용 시 end가 p번지로 이동 후 반복이 끝난다.)

4) 새로운 반복을 시작한다.

4-1) 세어둔 A, C, B, T의 개수가 조건에 부합하면 count를 1 증가한다.

4-2) start가 가리키는 번지의 문자가 A, C, B, T 중 하나라면 해당 문자의 개수를 1 감소한다.

4-3) start 번지수를 1 증가한다.

4-4) end가 가리키는 번지의 문자가 A, C, B, T 중 하나라면 해당 문자의 개수를 1 증가한다.

4-5) end 번지수를 1 증가한다.

5)  end가 s번지를 가리키면 모든 문자열을 검사했으므로 반복을 종료한다.

6) count를 출력한다.

 

이처럼, start와 end 사이를 검사 중인 문자열 구간으로 정하고 한 칸 우측으로 이동할 때 마다 A, C, G, T의 변화를 체크하며 조건에 맞는 문자열 구간의 수를 구한다.

 

 

코드 작성

#include <iostream>
using namespace std;

typedef struct ACGT {
    int a = 0;
    int c = 0;
    int g = 0;
    int t = 0;
} ACGT;  //가독성을 위해 a, c, g, t의 개수를 구조체로 관리

void setPlusACGT(int num, ACGT* flag) {
//end가 이동할 때, 새로 영역에 들어오는 문자를 판별 후 개수를 +1 해줌.
    switch(num) {
        case 'A' : flag->a++; break;
        case 'C' : flag->c++; break;
        case 'G' : flag->g++; break;
        case 'T' : flag->t++; break;
        default : break;;
    }
}

void setMinusACGT(int num, ACGT* flag) {
//start가 이동할 때, 영역에서 제외되는 (가장 앞) 문자를 판별 후 개수를 -1 해줌.
    switch(num) {
        case 'A' : flag->a--; break;
        case 'C' : flag->c--; break;
        case 'G' : flag->g--; break;
        case 'T' : flag->t--; break;
        default : break;;
    }
}

int main() {
    int s, p;
    scanf("%d %d\n", &s, &p);
    
    char str[s+1];
    scanf("%s\n", str);
    int a, c, g, t;
    scanf("%d %d %d %d", &a, &c, &g, &t);
    
    ACGT flag;
    int start=0, end=0, count=0;
    for ( ; end<p ; end++) { //end를 한 칸씩 이동하며 구간에 한 문자씩 포함함.
        setPlusACGT(str[end], &flag); //문자 개수 체크
    }
    
    while(end<=s) {
        if (flag.a>=a && flag.c>=c && flag.g>=g && flag.t>=t) {
        //현재 구간 속 문자열이 조건에 부합한다면 count++
            count++;
        }
        setMinusACGT(str[start++], &flag); //end의 이동에 따른 구간 내 문자 개수 체크
        setPlusACGT(str[end++], &flag); //start의 이동에 따른 구간 내 문자 개수 체크
    }
    
    printf("%d", count);
    
    
    return 0;
}