백준 1593번 문자 해독 (C++)

문제 링크 : www.acmicpc.net/problem/1593

1593번: 문자 해독

이 문제는 실수를 여러번 겪었다.

처음에는 문자열 W의 조합을 next_permutation 함수로 구하여 그 값을 찾는 과정을 진행했는데, 번번히 시간초과가 나왔다.

문제를 자세히 읽어보니 W의 길이는 최대 3000, S의 길이는 최대 3,000,000이라서 시간초과가 나올 수 밖에 없는 구조임을 깨달았다.

문자열 W의 조합 3000!만 고려해도 시간초과는 정해진 결과였다 😂

 

고민끝에 투 포인터, 그 중에서 슬라이딩 윈도우 기법을 활용하게 되었다.

슬라이딩 윈도우 기법이란 기본적으로 투 포인터와 동일한 방식이지만, 탐색 구간의 사이즈가 매번 고정적이라는 조건이 붙은 투 포인터 기법이다. 말 그대로 창문을 밀어 위치를 옮기지만 창문의 크기는 고정적이다는 말에서 유래된 알고리즘이다.

 

문제 풀이는 다음과 같다.

1. 값을 입력받고 unordered_map을 2개 구현한다.

1개는 문자열 w에 포함된 알파벳을 저장할 map이고, 다른 1개는 탐색 과정 중 w에 포함되지 않은 단어를 저장할 map이다.

    int n,m,ans=0;
    string w,s;
    cin >> n >> m;
    cin >> w >> s;
    unordered_map<char,int> mp;
    unordered_map<char,int> mp2;
    for(int i=0; i<w.size(); i++) mp[w[i]]++;

2. 먼저 탐색을 한 번 진행해준다. 아래 코드를 봐보자.

    bool ch = true; // 1
    for(int i=0; i<n; i++){ // 2
        if(mp.find(s[i])!=mp.end()) mp[s[i]]--;
        else mp2[s[i]]++;
    }
    for(auto[k,v] : mp) { // 3
        if(v!=0) {ch = false; break;}
    }
    if(ch){ // 4
        for(auto[k,v] : mp2) { 
            if(v!=0) ch = false;
        }
    }
    if(ch) ans++; // 5

1번의 bool문은 문자열 s에 w의 조합이 존재하는지를 판단하는 변수다.

2번 과정을 통해, 고정된 사이즈 n만큼 for문을 돌려 문자열 s에서 문자열 w에 있는 단어와 동일한 단어가 있는지 판단하게 된다.

만약 동일한 단어가 있다면 문자열 w의 단어가 저장되어있던 mp에서 해당 단어의 value값을 감소시킨다.

만약 동일한 단어가 없는 경우, 즉, 새로운 문자가 등장한 경우 mp2에 해당 문자를 저장해준다.

결국 mp와 mp2에 저장된 key값의 value가 모두 '0'이어야 문자열 s안에 문자열 w의 조합이 있음을 나타낸다.

때문에 3번~4번 for문의 경우, value값이 0이 아닌 경우 곧 바로 반복문을 종료해주면 된다.

마지막으로 ch가 true인 경우, 모든 value값이 0이라는 뜻이므로 ans값을 +1해주면 된다.

 

3. 다음은 슬라이딩 윈도우를 활용하여 탐색을 진행한다.

    int left = 0, right = n-1;
    while(n<m&&right<m){ // 1
        ch = true;
        if(mp.find(s[left])!=mp.end()) mp[s[left]]++; // 2
        else mp2[s[left]]--;
        left++; // 3
        right++;
        if(mp.find(s[right])!=mp.end()) mp[s[right]]--; // 4
        else mp2[s[right]]++;
        for(auto[k,v] : mp) { // 5
            if(v!=0) {ch = false; break;}
        }
        if(ch){
            for(auto[k,v] : mp2) {
                if(v!=0) {ch = false; break;}
            }
        }
        if(ch) ans++; // 6
    }
    cout << ans << "\n";

먼저 while문이 진행되는 조건은 n보다 m이 커야하며, right의 값은 m보다 작아야한다.

2번 과정은 left의 값을 초기화 시키고 left를 하나 증가시키는 과정이다.

만약 s[left]의 값이 mp에 저장이 되어있다면, 기존에 -1해주었던 값을 +1해주면 된다.

만약 위 조건이 충족되지 않을 경우 mp2에 저장되어있다는 뜻이므로, mp2에 해당 값을 -1해주면 된다.

그리고 3번 과정을 통해 left를 +1해주고 right을 +1해준다.

4번 과정은 새로이 추가된 right 위치의 값을 업데이트 하는 과정이다. mp에 해당 값이 있다면 -1을, 그렇지 않다면 mp2에 해당 값을 추가해주면 된다. 

5번 과정은 모든 key값의 value가 0인지를 판단하여 문자열 s안에 문자열 w의 조합이 있는지를 판단하는 과정이다.

만약 모든 value가 0이라면 ans값을 +1해주면 된다.

 

4. 답을 출력한다.

 

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,ans=0;
    string w,s;
    cin >> n >> m;
    cin >> w >> s;
    unordered_map<char,int> mp;
    unordered_map<char,int> mp2;
    for(int i=0; i<w.size(); i++) mp[w[i]]++;
    bool ch = true;
    int left = 0, right = n-1;
    for(int i=0; i<n; i++){
        if(mp.find(s[i])!=mp.end()) mp[s[i]]--;
        else mp2[s[i]]++;
    }
    for(auto[k,v] : mp) {
        if(v!=0) {ch = false; break;}
    }
    if(ch){
        for(auto[k,v] : mp2) {
            if(v!=0) {ch = false; break;}
        }
    }
    if(ch) ans++;
    while(n<m&&right<m){
        ch = true;
        if(mp.find(s[left])!=mp.end()) mp[s[left]]++;
        else mp2[s[left]]--;
        left++;
        right++;
        if(mp.find(s[right])!=mp.end()) mp[s[right]]--;
        else mp2[s[right]]++;
        for(auto[k,v] : mp) {
            if(v!=0) {ch = false; break;}
        }
        if(ch){
            for(auto[k,v] : mp2) {
                if(v!=0) {ch = false; break;}
            }
        }
        if(ch) ans++;
    }
    cout << ans << "\n";
    return 0;
}