BOJ 12891번: DNA 비밀번호

문제

---

문제 풀이1 - 시간 초과

문자열을 p의 개수만큼 옆으로 옮겨가며 검사

슬라이딩 윈도우 알고리즘

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

int rule[4];
int s, p, cnt;
string str;

void check(int idx) { // O(p)
    int a = 0, c = 0, g = 0, t = 0;
    for (int i = 0; i < p; i++) {
        if (str[idx + i] == 'A') { a++; }
        else if (str[idx + i] == 'C') { c++; }
        else if (str[idx + i] == 'G') { g++; }
        else { t++; }
    }
    if (a >= rule[0] && c >= rule[1] && g >= rule[2] && t >= rule[3]) { cnt++; }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> s >> p; // 입력
    cin >> str;
    for (int i = 0; i < 4; i++) { cin >> rule[i]; }

    for (int i = 0; i <= s - p; i++) { check(i); } // O(1+s-p)
    cout << cnt;

    return 0;
}

시간 복잡도 구하는 거 너무 어렵다
어떻게 하는 거지 왜 시간 초과지

---

문제 풀이2 - 맞았습니다!

문자열을 p의 개수만큼 옆으로 옮겨가며 검사
ㄴ 새로 검사가 아니라 바뀐 알파벳만 증감해줌

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

int rule[4];
int cnt, a, c, g, t;

void addCount(char i) {
    if (i == 'A') { a++; }
    else if (i == 'C') { c++; }
    else if (i == 'G') { g++; }
    else { t++; }
}

void minCount(char i) {
    if (i == 'A') { a--; }
    else if (i == 'C') { c--; }
    else if (i == 'G') { g--; }
    else { t--; }
}

void check() {
    if (a >= rule[0] && c >= rule[1] && g >= rule[2] && t >= rule[3]) { cnt++; }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int s, p;
    string str;

    cin >> s >> p; // 입력
    cin >> str;
    for (int i = 0; i < 4; i++) { cin >> rule[i]; }

    for (int i = 0; i < p; i++) { addCount(str[i]); } // 처음 비밀번호
    check();

    for (int i = p; i < s; i++) {
        minCount(str[i - p]); // 가장 앞의 알파벳 개수 감소
        addCount(str[i]); // 다음 알파벳 개수 증가
        check();
    }
    cout << cnt;

    return 0;
}

흐아아악.... 위의 함수에서 매개변수를 char c 로 해놓고 틀렸습니다 나오는 거에 아니 이게 왜 틀려 이러고 있었음.... VSC는 왜 이걸 되게 해준거야 너 때문이야 ㅠㅠㅠㅠㅠㅠ 바보