BOJ 4141 - Numbersrebmun

문제

BOJ 4141 - Numbersrebmun

전화기 키패드에서 알파벳 문자는 숫자에 대응된다. A, B, C는 2에, D, E, F는 3에, G, H, I는 4에, J, K, L은 5에, M, N, O는 6에, P, Q, R, S는 7에, T, U, V는 8에, W, X, Y, Z는 9에 대응된다. 주어진 단어의 각 알파벳을 대응하는 숫자로 변환한 뒤, 그 숫자열이 팰린드롬(앞뒤로 읽어도 같은 수열)인지 판별하는 문제이다.

입력

첫째 줄에 테스트 케이스 수 T가 주어진다. 이후 각 줄에 알파벳 소문자 또는 대문자로 이루어진 단어가 하나씩 주어진다.

출력

각 테스트 케이스마다 숫자열이 팰린드롬이면 YES, 아니면 NO를 출력한다.

예제

풀이

알파벳을 전화기 키패드 숫자 배열로 변환한 뒤, 팰린드롬 여부를 확인한다.

1. 소문자 입력을 대문자로 통일한다.
2. 각 알파벳을 미리 정의된 배열 asc[]를 이용해 숫자 문자로 변환한다.
3. 변환된 숫자 문자열과 그 역순 문자열을 비교한다.
4. 같으면 YES, 다르면 NO를 출력한다.

핵심 아이디어: 알파벳을 인덱스 0-25로 사용하여 asc[c - 'A']로 O(1)에 대응 숫자를 얻고, STL의 string 역방향 이터레이터로 팰린드롬을 판정한다.

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--)
  {
    string s, pn;
    cin >> s;
    int asc[26] = {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9};
    for (char &c : s)
    {
      if (c >= 'a')
        c -= ('a' - 'A');
      pn += to_string(asc[c - 'A']);
    }
    cout << (pn == string(pn.rbegin(), pn.rend()) ? "YES" : "NO") << '\n';
  }
}

복잡도

• 시간: O(N) — 문자열 길이 N에 대해 선형 탐색
• 공간: O(N) — 변환된 숫자 문자열 저장