개발 블로그

문제 링크 : https://www.acmicpc.net/problem/9046

문제

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

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

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

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

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

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

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

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

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

입력

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

출력

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

접근 방법

주의할 점 : getline(cin, str)으로 공백 포함한 한 줄을 받기 전에, cin>>T 이후의 입력 버퍼를 비우도록 하자!! 입력 버퍼 비우지 않으면 입력한 값을 T에 저장하고 남은 '\n'가 밀려서 그 다음의 getline(cin, str)의 str로 들어가게 돼서 입력값이 하나씩 밀리는 문제가 발생한다. 자세한 내용은 아래의 링크를 참고하자.

https://namwhis.tistory.com/entry/cin%EA%B3%BC-getline%EC%9D%84-%EA%B0%99%EC%9D%B4-%EC%82%AC%EC%9A%A9%ED%95%A0%EB%95%8C-cinignore%EC%9D%B4-%ED%95%84%EC%9A%94%ED%95%9C-%EC%9D%B4%EC%9C%A0-%EA%B8%B0%EB%A1%9D

1) T를 입력받은 후, cin.ingnore()을 이용하여 입력 버퍼를 비워준다. (다음에 공백을 포함한 문자열을 받아야 하기 때문에)

2) 각 테스트케이스는 소문자와 공백이므로, 각 소문자를 배열의 인덱스로 삼아서 ('a'가 아스키코드로 97이므로 97을 뺀 수를 인덱스로 삼는다) 해당 소문자가 몇번 나왔는지 수를 배열에 저장한다.

3) 가장 빈번하게 나타나는 문자가 여러개인지를 판단하기 위해 벡터에 pair를 넣는다. pair의 first는 문자가 출력된 수, pair의 second는 그 문자를 저장한다.

4) 벡터를 내림차순 정렬한다.

5) 가장 빈번하게 나타나는 문자가 여러개이면 vec[0].first 와 vec[1].first가 같을 것이기 때문에 이 경우에는 ?를 출력한다.

6) 이외에는 가장 빈번한 문자인 vec[i].second를 출력한다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;

int alphaCntArr[26] = {0,};
//a = 97
int main(){

   int T; cin >> T; cin.ignore();
   for(int t=1; t<=T; t++){
       memset(alphaCntArr, 0, sizeof(alphaCntArr));
       string str;
       getline(cin, str);

       for(int i = 0; i<str.length(); i++){
           if(str[i] == ' ') continue;

           alphaCntArr[str[i]-97]++;
       }

        vector<pair<int,char>> vec;
       for(int i = 0; i<26; i++){
           vec.push_back(make_pair(alphaCntArr[i], i+97));
       }

        sort(vec.begin(), vec.end(), greater<>());

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

    return 0;
}