BOJ 1593 : 문자 해독

• 문제 링크 : boj.kr/1593
• 난이도 : G5
• 태그 : 슬라이딩 윈도우

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int getNum(char c) {
    if(c <= 'Z') return c - 'A';
    return c - 'a' + 26;
}

bool check(vector<int>& a, vector<int>& b) {
    for(int i = 0; i < 52; i++) {
        if(a[i] != b[i]) return false;
    }
    return true;
}

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

    int n, m;
    cin >> n >> m;
    string w, s;
    cin >> w >> s;
    vector<int> target(52);
    for(auto u : w) target[getNum(u)]++;
    vector<int> cnt(52);
    for(int i = 0; i < n; i++) {
        cnt[getNum(s[i])]++;
    }
    int ans = 0;
    ans += check(target, cnt);
    for(int i = n; i < m; i++) {
        cnt[getNum(s[i])]++;
        cnt[getNum(s[i-n])]--;
        ans += check(target, cnt);
    }
    cout << ans;

    return 0;
}

---

풀이

가능한 문자의 수가 52개이므로 구간의 문자들의 수를 세면, O(52N)으로 해결 가능하다. 수를 셀 때 슬라이딩 윈도우 기법을 이요하면 O(1)로 갱신할 수 있다.