BOJ 12891 - DNA 비밀번호 (C++)

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

최초 풀이: 2025. 06. 01.

#sliding_window #string

아이디어

• 전형적인 'sliding_window' 문제이다.
• 0번째 index부터 시작하는 길이 |P|의 window를 잡아서 A, C, G, T 의 개수를 기록하고, 한 칸씩 이동하며 없어지는 문자와 새로 들어오는 문자를 확인하여 개수를 변화시켜주자.

Substrings vs Subsequences

• Substring: 원래의 문자열에서 연속된 구간을 떼어낸 부분 문자열이다.
  • 예: "abcdef"에서 "bcd"는 substring이다.
• Subsequence: 원래의 문자열에서 일부 문자를 선택하여 순서만 유지한 채 나열한 부분 문자열이다. 연속적일 필요는 없다.
  • 예: "abcdef"에서 "acf"는 subsequence이다. (연속되지 않아도 됨)

이 문제에서는 Substring을 요구한다는 점에 주의하자! (Subsequence가 아님!)

최초 풀이(C++)(내 풀이)

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int S, P;
    cin >> S >> P;

    string DNA;
    cin >> DNA;

    int A, C, G, T;
    cin >> A >> C >> G >> T;

    int num_A = 0, num_C = 0, num_G = 0, num_T = 0;
    int ans = 0;
    for(int i = 0; i < P; i++){
        if(DNA[i] == 'A') num_A++;
        else if(DNA[i] == 'C') num_C++;
        else if(DNA[i] == 'G') num_G++;
        else if(DNA[i] == 'T') num_T++;
    }

    if(num_A >= A && num_C >= C && num_G >= G && num_T >= T) ans++;
    
    for(int i = P; i < S; i++){
        if(DNA[i - P] == 'A') num_A--;
        else if(DNA[i - P] == 'C') num_C--;
        else if(DNA[i - P] == 'G') num_G--;
        else if(DNA[i - P] == 'T') num_T--;

        if(DNA[i] == 'A') num_A++;
        else if(DNA[i] == 'C') num_C++;
        else if(DNA[i] == 'G') num_G++;
        else if(DNA[i] == 'T') num_T++;

        if(num_A >= A && num_C >= C && num_G >= G && num_T >= T) ans++;
    }

    cout << ans;
    return 0;
}

개선된 풀이(by GPT)

#include <iostream>
#include <string>
using namespace std;

// 문자 인덱스 매핑 함수
int idx(char c) {
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    if (c == 'G') return 2;
    return 3; // 'T'
}

// 현재 윈도우의 카운트가 조건을 만족하는지 검사
bool is_valid(int count[], int required[]) {
    for (int i = 0; i < 4; ++i) {
        if (count[i] < required[i]) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int S, P;
    cin >> S >> P;
    string DNA;
    cin >> DNA;

    int required[4]; // A, C, G, T가 최소 몇 개 필요한지
    for (int i = 0; i < 4; ++i) cin >> required[i];
    int count[4] = {0,}; // 현재 윈도우의 A, C, G, T 개수

    // 초기 윈도우 설정
    for (int i = 0; i < P; ++i) {
        count[idx(DNA[i])]++;
    }

    int ans = 0;
    if (is_valid(count, required)) ans++;

    // 슬라이딩 윈도우
    for (int i = P; i < S; ++i) {
        count[idx(DNA[i - P])]--; // 왼쪽 문자 제거
        count[idx(DNA[i])]++;     // 오른쪽 문자 추가
        if (is_valid(count, required)) ans++;
    }

    cout << ans << '\n';
    return 0;
}

• 내 풀이를 작성할 때 main문이 지저분하다고 생각하였는데, 이런 식으로 함수를 이용하면 조금 더 깔끔하게 풀이를 적을 수 있을 것 같다.