[BOJ] 9369 : 암호 깨기

9369 : 암호 깨기

풀이

구현

1:1 영단어로 매칭되는 암호문을 찾은 후 target 암호문을 해독하는 문제이다.

모르는 영단어가 나오거나, 복수의 암호문이 매칭될때 충돌한다면 ?를 출력한다.

(이때 여러가지 암호문이 가능하지만 모든게 충돌하면 ????가 나와도 괜찮다)

배열을 크게잡고 착실히 문제를 풀었는데, 틀렸다고 나왔다.

반례는 바로~~ 26개 알파벳중에 25개를 알게되었다면 나머지 하나도 유추 할 수 있다는 점이었다.

abcdefghijklmnopqrstuvwxy

abcdefghijklmnopqrstuvwxy

abcz

이렇다면 z는 z란것을 유추가 가능하다.

이부분을 추가하니 짧은시간(16ms)에 문제를 해결할 수 있었다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <queue>
using namespace std;

vector<string> vs;
int chk[100][150];
int chk2[100][150];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    cin>>T;
    while(T--){
        memset(chk,0,sizeof(chk));
        memset(chk2,0,sizeof(chk2));
        vs.clear();
        
        //ok idx
        vector<int> ok;
        
        int n;
        cin>>n;
        string str;
        for(int i=0;i<n;i++){
            cin>>str;
            vs.push_back(str);
        }
        string correct;
        cin>>correct;
        string target;
        cin>>target;
        
        for(int i=0;i<n;i++){
            int flag=0;
            int cnt=0;
            for(int j=0;j<correct.size();j++){
                if(vs[i].size() != correct.size()){
                    flag=1;
                    break;
                }
                
                if(chk[i][vs[i][j]]==0 && chk2[i][correct[j]]==0){
                    chk[i][vs[i][j]]=correct[j];
                    chk2[i][correct[j]]=vs[i][j];
                    cnt++;
                }else if(chk2[i][correct[j]]!=vs[i][j] || chk[i][vs[i][j]]!=correct[j]){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                ok.push_back(i);
                //25개알면 나머지 하나 계산가능
                if(cnt==25){
                    int a=0,b=0;
                    for(int j=97;j<=122;j++){
                        if(chk[i][j]==0){
                            a=j;
                        }
                        if(chk2[i][j]==0){
                            b=j;
                        }
                    }
                    chk[i][a]=b;
                    chk2[i][b]=a;
                }
            }
        }
        
        if(ok.size()==0){
            cout<<"IMPOSSIBLE"<<'\n';
        }else{
            //target해독후 출력
            if(ok.size()==1){
                int idx = ok[0];
                string ans;
                for(int i=0;i<target.size();i++){
                    if(chk[idx][target[i]]==0){
                        ans.push_back('?');
                    }else{
                        ans.push_back(chk[idx][target[i]]);
                    }
                }
                cout<<ans<<'\n';
            }
            else{
                string ans;
                for(int i=0;i<target.size();i++){
                    int flag=0;
                    int idx=ok[0];
                    if(chk[idx][target[i]]==0){
                        ans.push_back('?');
                        continue;
                    }
                    int num = chk[idx][target[i]];
                    for(int j=1;j<ok.size();j++){
                        if(num!=chk[ok[j]][target[i]]){
                            flag=1;
                            break;
                        }
                    }
                    if(flag){
                        ans.push_back('?');
                    }else{
                        ans.push_back(num);
                    }
                }
                cout<<ans<<'\n';
            }
        }
    }
    return 0;
}

Written on April 29, 2019