[백준] 12891번 : DNA 비밀번호

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

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

int alphabetIntoindex(char alphabet) {
    switch (alphabet) {
        case 'A':
            return 0;
        case 'C':
            return 1;
        case 'G':
            return 2;
        case 'T':
            return 3;
    }
}

bool isOk(int check[], int my[]) {
    for (int i = 0; i < 4; i++) {
        if (check[i] > my[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    int S;
    int P;
    int answer = 0;
    string dna;
    int check[4] = { 0 };
    int my[4] = { 0 };

    cin >> S >> P;
    cin >> dna;

    for (int i = 0; i < 4; i++) {
        cin >> check[i];
    }

    for (int i = 0; i < P; i++) {
        my[alphabetIntoindex(dna[i])]++;
    }

    if (isOk(check, my)) {
        answer++;
    }

    for (int i = P; i < S; i++) {
        int j = i - P;

        my[alphabetIntoindex(dna[i])]++;
        my[alphabetIntoindex(dna[j])]--;

        if (isOk(check, my)) {
            answer++;
        }
    }

    cout << answer << "\n";

    return 0;
}

---

📝 풀이

윈도우 슬라이딩 기법을 사용하여 문제를 풀었습니다.

처음 윈도우에 주어준 DNA 문자열의 0부터 P까지를 추가합니다.

그리고 윈도우가 비밀번호로 가능한지 확인합니다.

 

그 후 윈도우를 한 칸씩 뒤로 밀어 현재 DNA 갯수를 갱신합니다.

갱신 후에는 부분 문자열이 비밀번호로 가능한지 확인합니다.

 

DNA 문자열의 마지막까지 비교하였으면 최종 answer 값을 출력합니다.