백준 4422, Crypt Kicker II

개요

문제 링크
골드 4, String, Hash
Permutation을 이용해 문자열 decoding

---

접근

1. 문제 해석이 조금 까다로울 수 있는데, 각각의 알파벳을 일대일 대응으로 변환한 암호문이 주어지면 원문을 복원하는 문제이다. 이때 복원 규칙을 알 수 있도록 특정 문장을 사용했는데, 그 문장이 바로

   the quick brown fox jumps over the lazy dog

   이다. 따라서 저 문장의 암호화로 나올 수 있는 문장을 찾은 뒤, 규칙을 설정하고 복호화해서 출력하면 된다.

2. 그럼 변환 가능성은 어떻게 판단하냐? 하면 여러 방법이 있겠지만 나는 모든 알파벳의 위치를 저장한 뒤, 위치 집합이 같은지 봤다. 어떤 알파벳인지 몰라도 된다. 예를들어 {(1,3), (2,5,6), (4)}와 같이 위치 정보가 같다면 암호화 가능한 문장이 된다.

3. 여기서 C++의 미친 장점, vector를 잘 활용하면 벡터 간의 == 연산은 기본적으로 제공되므로 아주 쉽게 구현해줄 수 있다.

나머지는 문제 번역 이외에 크게 어려울 부분은 없다.

---

Pseudo code

indexSet() {
    index[26] = vector<vector>
    for (x: string)
        for (i = 0~26)
            if (x == 'a'+i)
                index[i].push(x.index)
    return sorted(index)
}
if (indexSet(input) == indexSet(FOX))
    for (i = 0~input.size())
        rule[input[i]] = FOX[i]
        // rule = map<char,char>

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()
using str=string;
using vec=vector<str>;
using vii=vector<int>;
using mat=vector<vii>;
str pt="the quick brown fox jumps over the lazy dog";
map<char,char> rule;

mat get(str s) {
    mat t(26);
    int n=s.size();
    for (int i=0;i<26;i++)
        for (int j=0;j<n;j++)
            if (s[j]=='a'+i)
                t[i].pb(j);
    sort(all(t));
    return t;
}

int main() {
    mat ms=get(pt);
    str s;
    vec enc;
    bool ch=0;
    while(getline(cin,s)) {
        enc.pb(s);
        if (get(s)==ms) {
            ch=1;
            int n=s.size();
            for (int i=0;i<n;i++)
                rule[s[i]]=pt[i];
        }
    }
    if (!ch) cout<<"No solution.";
    else for (auto s:enc) {
        for (auto x:s)
            cout<<rule[x];
        cout<<"\n";
    }
}