[Baekjoon] 1593번: 문자 해독(c++)

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

1593번: 문자 해독



문제를 보고 순열으로 풀면 되겠다 싶어서 next_permutation를 써서 순열을 만들고 풀려했는데, 계속 시간초과가 났다.

찾아보니 (1≤g≤3000) 조건때문에, next_permutation으로 순열을 만들경우 3000!라서 시간초과가 나는것이 당연했다...

시간초과를 어떻게해결해야할지 감이안잡혀서 구글검색을 통해 풀었다 ㅠㅠ

https://astrid-dm.tistory.com/381 이분의 블로그를 참고했다!

 

사실 풀이법을 봐도 이해가 되지않아서 한참 헤맸다 ㅠㅠ

n = w의 길이

m = s의 길이

w = 찾고자하는 단어

s = 벽화에서 추출한 단어

 

exist = 존재하는 문자

no_exist = 존재하지 않는 문자

 

exist와 no_exist의 값이 모두 0일때, answer를 증가시키는 것이 목적.

 

맨 처음 exist에서 w의 키값 자리에 모두 +1씩 초기화한다.

처음 반복문으로 0~3 까지 (0~n-1)  s에 대한 w길이만큼 비교한다. 

     - s에 대하여 w에 해당하는 문자가 있다면 exist에서 s[i]--

     - 문자가 없다면 no_exist s[i]++

     - exist, no_exist 모두0이면 answer++

while문 부터는 문자를 left에서 right까지 하나씩 지워가는 의미로 본다.

맨처음 w(=4)자리수만큼 비교했으므로, 

left = 0, right = 3일때

exist 에 s[0]값이 있다면 exist[ 'A' ]++; /  없다면 no_exist[ 'A' ]--;

 

left = 1, right = 4일때 

exist에 s[4]인 c값이 있다면 exist[ 'c' ] --; / 없다면 no_exist['c']++;

 

즉 left에서는 exist안에 해당문자가 있을때 ++ 시키고, right에서는 exist안에 해당문자가 있을때 --를 시킨다.

*left에서는 그 문자를 제외시킨다 ( 실제로는 +1 ),

right에서는 그 문자를 포함시킨다 ( 실제로는 -1 )로 이해해서 풀었다. (n사이즈만큼 유지)

예시로 표현하면
👉left = 0 일때

exist[ 'A' ] 값이 있으므로 exist[ 'A' ] ++;

 

👉right = 4

exist[ 'c' ] 값이 있으므로 exist[ 'c' ] --;

👉left = 1

exist[ 'b' ] 값이 없으므로 no_exist[ 'b' ] --;

 

👉right = 5

exist[ 'a' ] 값이 있으므로 exist[ 'a' ] --;

👉left = 2

exist[ 'r' ] 값이 없으므로 no_exist[ 'r' ] --;

 

👉right = 6 

exist[ 'd' ] 값이 있으므로 exist[ 'd' ] --;

👉left = 3

exist[ 'A' ] 값이 있으므로 exist[ 'A' ] ++;

 

👉right = 7 

exist[ 'A' ] 값이 있으므로 exist[ 'A' ] --;

👉left = 4

exist[ 'c' ] 값이 있으므로 exist[ 'c' ] ++;

 

👉right = 8

exist[ 'b' ] 값이 없으므로 no_exist[ 'b' ] ++;

👉left = 5

exist[ 'a' ] 값이 있으므로 exist[ 'a' ] ++;

 

👉right = 9일때

exist[ 'R' ] 값이 없으므로 no_exist[ 'R' ] ++;

👉left = 6

exist[ 'd' ] 값이 있으므로 exist[ 'd' ] ++;

 

👉right = 10일때

exist[ 'a' ] 값이 있으므로 exist['a'] ++;

 

 

---

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

unordered_map<char, int>exist;
unordered_map<char, int>no_exist;
bool flag = true;
int answer=0;

void check(){
    for(auto[key,value] : exist){
        if(value != 0) {flag = false; break;}
    }
    if(flag)for(auto[key,value] : no_exist){
        if(value != 0) {flag = false; break;}
    }
    if(flag)answer++;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    int n,m;
    string w,s;
    
    cin >> n >> m;
    cin >> w >> s;

    for(int i=0;i<n;i++)exist[w[i]]++;
    for(int i=0;i<n;i++){
        if(exist.find(s[i]) != exist.end()) exist[s[i]]--;
        else no_exist[s[i]]++;
    }
    
    check();
    
    int left = -1, right = n-1;
    while(right <= m){
        flag = true;
        
        left++;
        
            if(exist.find(s[left]) != exist.end()) exist[s[left]]++;
            else no_exist[s[left]]--;
        
        right++;
        
            if(exist.find(s[right]) != exist.end()) exist[s[right]]--;
            else no_exist[s[right]]++;
        
        check();
        
    }
    
    cout << answer;
    return 0;
}

 

+unordered_map 1개로 풀기

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

unordered_map<char, int> sum;
int answer = 0;
bool flag = true;
void chk(){
	//모두 다 0일때만 answer++
    for(auto[key,value] : sum){
           if(value != 0) {flag = false; break;}
       }
    if(flag) answer++;
}

int main() {

    int W, S;
    string w, s;
    cin >> W >> S;
    cin >> w >> s;
    
    for(int i=0;i<W;i++){
        sum[ w[i] ]++;
    }
    for(int i=0;i<W;i++){
         sum[ s[i] ]--;
    }
    chk();
    
    int left = 0, right = W;
    while (right != S) {
        flag = true;
        sum[ s[left] ] ++;
        left++;
        
        sum[ s[right] ] --;
        right++;
        chk();
    }
 
    cout << answer;
    
    return 0;
}