[C++] 백준 23084번: IUPC와 비밀번호 - Sliding Window

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

23084번: IUPC와 비밀번호

 

종강 이후 거진 두 달만에 하는 PS

문제를 읽어보니

1. 출력하는 문자는 모두 대문자이다.
2. 처음 비밀번호보다 작은 길이의 문자열은 존재할 수 없다.
3. 길이가 같은 문자열이라면 반드시 하나만 달라야 한다.
4. 길이가 다르다면 해당 문자열이 존재하거나, 해당 문자열의 길이 - 1 이 일치하는 문자열이 존재해야 한다.

위 네 가지 조건만 만족하면 문자열을 쉽게 찾을 수 있었다.

 

그런데 문제를 풀면서 4번 조건에서 삽질을 상당히 했다.

단순히 문자열을 비교해가며 존재하는 알파벳 개수와 존재하지 않아도 되는 알파벳 개수를 세면 되는 문제인데,

오랜만에 하는 PS라 그런지 되게 복잡하게 코드를 짜서 그런지 비교를 할 때 애를 먹었다.

 

먼저 길이 비교를 통해 길이가 작다면 무조건 NO를 출력하도록 설정했다.

다음은 길이가 같은 문자열을 비교하는 경우를 설정해 주었는데,

만약 존재하지 않는 문자라면 one 변수를 true로, 존재하지 않는 문자가 두 번 이상 나왔다면

two 변수까지 true로 바꾸어주었다.

결국 one 변수가 true가 아니거나 (모두 일치하는 경우), two 변수가 true인 경우(존재하지 않는 문자가 여러개인 경우) NO를 출력하도록 설정했다.

 

상당히 애를 먹은 마지막 비교는 문자열의 길이가 긴 경우이다.

만약 어떤 문자에 대해 현재까지 주어진 S에 존재하는 문자의 개수와 동일하게 나타났는데,

해당 문자가 중간에 또 튀어나오는 경우를 생각해보았다.

 

예를 들면, 

내가 필요한 문자 a의 개수는 3개이고, 현재까지 3개가 나온 상황인 경우

a가 다시 한 번 나온다면 해당 a는 4개로 처리하는 것이 아니라 

앞서 나온 a의 위치에따라 새로 갱신을 해주어야한다.

 

즉, 문자의 위치에 따라 수시로 업데이트를 해주어야한다는 소리인데,

귀찮아서 그냥 한 번에 배열에 저장하고, 한 번에 개수를 세주는 방식으로 코드를 짰다.

 

#include <iostream>
#include <queue>
#define rep(a,b) for(int i=a; i<b; i++)
using namespace std;
int al[26], dp[26];
queue<int>q;
bool one, two;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s, c; cin >> s;
    int n, cnt, o=0; cin >> n;
    rep(0,s.length()) al[s[i]-'a']++;
    while(n--){
        one=two=false;
        cnt=0;
        cin >> c;
        if(c.length()<s.length()) cout << "NO\n";
        else if(c.length()==s.length()){
            rep(0, c.length()){
                if(al[c[i]-'a'] && al[c[i]-'a']>dp[c[i]-'a']) dp[c[i]-'a']++;
                else one ? two=true : one=true;
            }
            if(!one || two) cout << "NO\n";
            else cout << "YES\n";
        }
        else{
            rep(0, c.length()){
                q.push(c[i]-'a');
                if(q.size()<=s.length()){
                    if(al[c[i]-'a']){
                        dp[c[i]-'a']++;
                        if(al[c[i]-'a']>=dp[c[i]-'a']) cnt++;
                    }
                    if(q.size()==s.length()){
                        if(cnt>=s.length()-1){
                            two=true;
                            break;
                        }
                    }
                }
                else{
                    if(al[q.front()]){
                        cnt-=min(al[q.front()],dp[q.front()]);
                        dp[q.front()]--;
                        cnt+=min(al[q.front()],dp[q.front()]);
                    }
                    if(al[c[i]-'a']){
                        cnt-=min(al[c[i]-'a'],dp[c[i]-'a']);
                        dp[c[i]-'a']++;
                        cnt+=min(al[c[i]-'a'],dp[c[i]-'a']);
                    }
                    q.pop();
                    if(cnt>=s.length()-1){
                        two=true;
                        break;
                    }
                }
            }
            if(cnt>=s.length()-1) two=true;
            two ? cout << "YES\n" : cout << "NO\n";
            while(!q.empty()) q.pop();
        }
        rep(0,26) dp[i]=0;
    }
}