[BOJ] #9046 - 복호화
👻 복호화
🌱 문제
암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.
가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.
예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.
평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz 암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz 위에 주어진 치환 방법을 통해 암호화하면 평문 “hello there”은 “xvssc kxvbv”가 된다.
한 가지 흥미로운 점은 영어 문법 특성상, 알파벳 ‘e’가 다른 영문 알파벳에 비해 자주 쓰인다는 것이다.
즉, 암호문 알파벳 대치표 없이 암호문을 복호화하려 할 때, 암호문 알파벳 빈도수를 체크하면 암호문 알파벳 > 빈도수 중 가장 빈번하게 나타나는 알파벳이 ‘e’라는 사실을 유추해볼 수 있다.
위 방법으로 암호문 알파벳의 빈도수를 체크하고, 가장 빈번하게 나타나는 문자를 출력하는 프로그램을 > 작성하면 된다.
만약 주어진 암호문에서 가장 빈번하게 나타나는 문자가 여러 개일 경우, 그 빈번한 문자 중 어느 것이 평문 > 알파벳 ‘e’를 가리키는지 확실하게 알 수 없기 때문에 “모르겠음”을 의미하는 ‘?’를 출력하면 된다.
- 시간 제한 : 1초
- 메모리 제한 : 128 MB
🌱 입력
입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이며 255이하다.
🌱 출력
각각의 테스트 케이스에 대해, 가장 빈번하게 나타나는 문자를 출력하거나 빈번하게 나타나는 문자가 여러 개일 경우 ‘?’를 출력한다.
🌱 예제
🪐 입출력 1
- 입력
3 asvdge ef ofmdofn xvssc kxvbv hull full suua pmlu - 출력
f v ?
👻 풀이
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define PCI pair<char, int>
int T;
string s;
vector<char> ret;
bool cmp(const PCI& a, const PCI& b)
{
return a.second > b.second;
}
int main()
{
// 복호화
cin >> T;
cin.ignore();
for (int i = 0; i < T; i++)
{
getline(cin, s);
map<char, int> m;
int cnt = 0;
while (s[cnt])
{
if (s[cnt] == ' ')
{
cnt++;
continue;
}
if (m.count(s[cnt]) > 0)
m[s[cnt]]++;
else
m.insert({ s[cnt], 1 });
cnt++;
}
vector<PCI> vec(m.begin(), m.end());
sort(vec.begin(), vec.end(), cmp);
if (vec.size() == 1)
ret.push_back(vec[0].first);
else
{
if (vec[0].second == vec[1].second)
ret.push_back('?');
else
ret.push_back(vec[0].first);
}
}
for (auto it : ret) cout << it << '\n';
return 0;
}
- 시간 : 0 ms
- 메모리 : 2032 KB
👻 글을 마치며
이 문제는 브론즈 2단계인가였던 것 같다. 어제부터 붙잡고 있었던 문제였는데 이상하게 머리가 안 돌아가서 오늘에서야 풀었다. 오늘 다시 하니까 금방 푼 것 같긴하다. 이상하게 배열..이 기억이 안나서 이 부분은 복습이 많이 필요할 것 같다. 그리고 다른 사람들 풀이를 보는데 이해가 안 가는 코드가 아직은 많은 것 같다.. 한 부분씩 차근차근 리뷰하면서 공부해야할 것 같다. 차이점을 알아야 어느 걸 써야할 지 아니까.. 🥲
Leave a comment