백준 9046 복호화 c++ (문자열)

문제 출처 : https://www.acmicpc.net/problem/9046

9046번: 복호화

문제

암호학에서 치환 암호(substitution cipher)란, 평문에 들어있는 각각의 문자를 주어진 치환 방법으로 암호화하는 방법 중 하나다.

가장 단순한 방법은 평문의 알파벳을 암호문의 알파벳으로 대치시켜 치환시키는 것이다.

예를 들어, 아래와 같은 알파벳 대치표가 주어졌다고 하자.

• 평문 알파벳 대치표 : abcdefghijklmnopqrstuvwxyz
• 암호문 알파벳 대치표 : wghuvijxpqrstacdebfklmnoyz

위에 주어진 치환 방법을 통해 암호화하면 평문 "hello there"은 "xvssc kxvbv"가 된다.

한 가지 흥미로운 점은 영어 문법 특성상, 알파벳 'e'가 다른 영문 알파벳에 비해 자주 쓰인다는 것이다.

즉, 암호문 알파벳 대치표 없이 암호문을 복호화하려 할 때, 암호문 알파벳 빈도수를 체크하면 암호문 알파벳 빈도수 중 가장 빈번하게 나타나는 알파벳이 'e'라는 사실을 유추해볼 수 있다.

위 방법으로 암호문 알파벳의 빈도수를 체크하고, 가장 빈번하게 나타나는 문자를 출력하는 프로그램을 작성하면 된다.

만약 주어진 암호문에서 가장 빈번하게 나타나는 문자가 여러 개일 경우, 그 빈번한 문자 중 어느 것이 평문 알파벳 'e'를 가리키는지 확실하게 알 수 없기 때문에 "모르겠음"을 의미하는 '?'를 출력하면 된다.

입력

입력의 T(1 ≤ T ≤ 20)는 테스트 케이스로, 입력 제일 상단에 주어진다. 각각의 테스트 케이스는 한 줄마다 소문자와 공백으로 이루어진 영어 문장이 주어진다. 이 문장의 길이는 적어도 1이상이며 255이하다.

출력

각각의 테스트 케이스에 대해, 가장 빈번하게 나타나는 문자를 출력하거나 빈번하게 나타나는 문자가 여러 개일 경우 '?'를 출력한다.

알고리즘 분류

• 구현
• 문자열

풀이

kotlin, java, c++ 세 개의 언어로 문제를 푸는 나에게, 정렬 커스텀, 공백 문자열 입력 등을 익히기 굉장히 좋은 문제이다.

풀이는, 각 테스트케이스마다 한 줄을 string으로 받아 문자들을 검사하며, 공백이 아닐 경우에는 아스키 코드를 이용한 int형 문자 배열에 문자가 나온 수와 문자를 저장한다. 이후 문자가 나온 수 기준으로 내림차순 정렬하고, 첫 번째 인덱스와 두 번째 인덱스가 같은 경우 ?를 출력하고, 아니면 첫 번째 인덱스의 문자를 출력한다. 

 

코드

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

bool cmp(pair<int,char> a, pair<int,char> b) {
	return a.first > b.first;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;
	cin >> t;
	cin.ignore();
	while (t--) {
		string sen;
		getline(cin, sen);
		pair<int, char> chList[26] = { {0,' '} };
		for (int i = 0; i < sen.length(); i++) {
			if (isspace(sen[i])) continue;
			chList[sen[i] - 'a'] = { chList[sen[i] - 'a'].first+1,sen[i] };
		}
		sort(chList, chList + 26, cmp);

		if (chList[0].first != chList[1].first) {
			cout << chList[0].second<<'\n';
		}
		else {
			cout << '?' << '\n';
		}
		
	}



	return 0;
}