[BOJ/백준][Gold4] 1593 : 문자 해독 (C++)

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

1593번: 문자 해독

 

 

[난이도] Gold4
[유형] 슬라이딩 윈도우

[풀이]
w의 모든 순열을 구해서 풀기에는 최대 길이가 3000이므로 너무 많은 연산이 필요합니다.

s에 포함되어 있는 연속된 w의 순열을 찾기만 하면 된다는 것을 이용하면 O(M) (s의 길이 M) 에 해결이 가능합니다.

w의 길이가 N, s의 길이가 M일 때,
s에 포함된 w의 순열은 길이가 N이면서 w에 포함된 모든 알파벳을 하나도 빠짐없이 사용할 string을 찾으면 됩니다.

wcnt[100], scnt[100]을 선언하여 wcnt[100]에는 w의 각 문자가 몇개씩 들어있지를 저장해놓고,

현재 확인중인 문자열의 맨 앞 index를 의미하는 sidx를 0으로 설정해놓고.
s의 0번 문자부터 확인하면서 아래와 같이 처리해줍니다.

현재 확인 중인 i번째 문자가 c일 때,
c = s[i]
if scnt[c-'A'] < wcnt[c-'A']
    c는 최대 wcnt[c-'A']만큼 사용이 가능한데 아직 scnt[c-'A']에 여유가 있으므로
    문자열에 포함시켜 주고 snct[c-'A']++ 를 해줍니다.

else
    wcnt[c-'A']를 모두 사용하였으므로 현재 문자 c를 문자열에 포함시킬 수 없습니다.
    c가 나올 때까지 sidx를 뒤로 옮기며 scnt 배열을 수정해줍니다. c가 j번째 index에 나온다면
    sidx를 j+1로 수정해주면 i번 문자 c를 포함시킬 수 있게 됩니다.
    만약 c를 발견하지 못했다면 wcnt[c-'A']==0 이라는 의미이고 sidx i+1부터 하여 다시 탐색을 시작해야 합니다.

매 루프마다 i-sidx+1==N 를 만족한다면 길이가 N인 w의 수열을 찾은 것이므로 ans++을 해줍니다.

 

 

#include <iostream>
#include <string>
using namespace std;
string w,s;
int N,M,wcnt[100],scnt[100],ans;
int main(){
    cin >> N>>M>>w>>s;
    for(auto c : w) wcnt[c-'A']++;
    int sidx=0;
    for(int i=0;i<M;i++){
        char c = s[i];
        if(scnt[c-'A'] < wcnt[c-'A']){
            scnt[c-'A']++;
        }else{
            for(int j=sidx;j<=i;j++){
                if(s[i]==s[j]){
                    sidx=j+1;
                    break;
                }
                scnt[s[j]-'A']--;
            }
        }
        if(i-sidx+1==N) ans++;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1593.cpp