백준 1593번. 문자 해독(c++) / 문자열 처리

생각보다 까다로웠던 문제?

시간초과와 틀렸습니다 늪에 빠져 푸는 데에 오래걸렸다....

 

sliding window문제!!

그냥 해독하려는 문자열을 기준으로 찾고자 하는 단어의 크기만큼 (g만큼) 길이를 잡아서

w문자열과 종류가 같고 개수도 같은지 확인하면 된다.

 

나는 map을 사용하여 종류와 개수를 판단했다.

 

// 문자해독 (sliding window)
#include <map>
#include <iostream>
using namespace std;
 
int n, m;
string w, s;
map<char, int> origin; // w문자열에서의 구성글자
map<char, int> tmp; // s문자열에서의 구성글자(w문자열의 길이만큼 슬라이딩 윈도우로 계산)
int kind = 0; // w문자열의 종류
int num = 0; // s문자열의 종류(w문자열의 길이만큼 슬라이딩 윈도우로 계산)
int ans = 0;
 
int main()
{
    cin>>n>>m;
    cin>>w>>s;
 
    for(int i=0; i<n; i++){
        if(origin.count(w[i])==0){
            origin[w[i]] = 1;
            kind++;
        }else{
            origin[w[i]]++;
        }
    }
 
    int Start = 0;
    int End = n-1;
 
    // s문자열에서 처음 n개의 문자에 대해 계산
    for(int i=0; i<n; i++){
        if(tmp.count(s[i])==0){
            tmp[s[i]] = 1;
            num++;
        }else{
            tmp[s[i]]++;
        }
    }
 
    while(1)
    {
        if(num==kind){
            bool check = true;
            for(int i=Start; i<=End; i++){
                if(tmp[s[i]]!=origin[s[i]]){
                    check = false;
                    break;
                }
            }
            if(check) ans++;
        }
 
        // Start값 조정
        if(tmp[s[Start]]==1){
            tmp.erase(s[Start]);
            num--;
        }else{
            tmp[s[Start]]--;
        }
        Start++;
 
        // End값 조정
        End++;
        if(End>=m) break;
    
        if(tmp.count(s[End])==0){
            tmp[s[End]] = 1;
            num++;
        }else{
            tmp[s[End]]++;
        }
    }
 
    cout<<ans<<"\n";
    return 0;
}

 

 

문제 첨부

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

1593번: 문자 해독