BOJ 9046 - 복호화

문제

BOJ 9046 - 복호화

카이사르 암호(Caesar Cipher)는 알파벳을 일정한 거리만큼 밀어서 치환하는 암호 방식이다. 암호문에서 가장 많이 등장하는 알파벳이 원문의 e에 해당한다는 가정 하에, 해당 문자를 찾는다. 최빈 문자가 두 개 이상이면 ?를 출력한다.

입력

첫 번째 줄에 테스트 케이스 수 T가 주어진다. 각 테스트 케이스마다 공백과 알파벳 소문자로 구성된 한 줄의 암호문이 주어진다.

출력

각 테스트 케이스에 대해 가장 많이 등장하는 알파벳 한 글자를 출력한다. 최빈 문자가 두 개 이상이면 ?를 출력한다.

예제

풀이

각 알파벳의 등장 횟수를 세어 최빈 문자가 유일한지 확인한다.

1. T개의 테스트 케이스를 처리한다.
2. 각 줄을 getline으로 읽고 알파벳 문자에 대해서만 빈도를 카운트한다.
3. 카운트 맵을 순회하면서 현재 최대 빈도보다 큰 값이 나오면 최빈 문자를 갱신한다.
4. 동일한 빈도의 문자가 또 나오면 결과를 ?로 설정한다.
5. 결과를 출력한다.

핵심 아이디어: 최빈 문자를 추적하면서 동수인 경우를 ?로 처리하면 된다. unordered_map으로 빈도를 집계하고, 최댓값 갱신 시 단일 최빈값, 동일 빈도 발견 시 ?로 즉시 전환하는 방식이다.

코드

#include <iostream>
#include <unordered_map>
 
using namespace std;
 
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
 
  int T;
  cin >> T;
  cin.ignore();
  while (T--)
  {
    unordered_map<char, int> m;
    string s;
    int cnt = 0;
    char res = '?';
    getline(cin, s);
    for (char a : s)
    {
      if (a >= 'A' && a <= 'z')
      {
        m[a]++;
      }
    }
    for (auto a : m)
    {
      if (a.second > cnt)
      {
        cnt = a.second;
        res = a.first;
      }
      else if (a.second == cnt)
        res = '?';
    }
    cout << res << '\n';
  }
  return 0;
}

복잡도

• 시간: O(N) — 문자열 길이 N에 대해 1회 순회 (알파벳 종류 최대 26개로 맵 순회는 상수)
• 공간: O(1) — 알파벳 26자 이하의 고정 크기 맵