C++로 전화번호 숫자로 만들 수 있는 모든 단어 출력하기

문제 개요

이 문제에서는 하나의 숫자열이 주어지며, 구식 휴대폰 키패드에서 해당 숫자들을 차례로 눌러 만들 수 있는 모든 단어를 출력해야 합니다.

구식 휴대폰 키패드의 이해

오늘날 우리가 사용하는 QWERTY 자판은 매우 익숙하지만, QWERTY 자판이 보급되기 전의 휴대폰에는 숫자와 알파벳이 함께 인쇄된 12버튼 키패드가 장착되어 있었습니다. 예를 들어 6번 버튼에는 'MNO'가 배치되어 있어, 버튼을 한 번, 두 번, 세 번 눌러 각각 M, N, O를 입력할 수 있었습니다.

당시 키패드의 배치는 다음과 같습니다.

이 키패드에도 모든 알파벳이 존재하기 때문에 사용자는 충분히 문자를 입력할 수 있었습니다. 따라서 이 문제의 목표는 주어진 숫자 시퀀스로 생성 가능한 모든 단어 조합을 출력하는 것입니다.

예시

예를 들어 숫자 687이 입력으로 주어졌다고 가정해 보겠습니다.

입력: 687

출력: mtp mtq mtr mts mup muq mur mus mvp mvq mvr mvs
ntp ntq ntr nts nup nuq nur nus nvp nvq nvr nvs
otp otq otr ots oup ouq our ous ovp ovq ovr ovs

접근 방법: 재귀 활용

위 예시에서 드러나는 패턴을 살펴보면, 각 버튼에는 고유한 문자 집합이 연결되어 있으며 입력 시 이 문자들을 사용하게 됩니다. 즉, 각 숫자마다 최대 4가지 후보 문자(7은 PQRS, 9는 WXYZ인 경우)가 존재합니다.

따라서 첫 번째 자릿수의 문자를 하나 고정한 뒤 다음 자릿수로 넘어가며 단어를 완성하고, 마지막 자릿수까지 도달하면 완성된 단어를 출력하는 방식으로 문제를 해결할 수 있습니다. 이 과정은 재귀 호출로 자연스럽게 구현됩니다.

C++ 구현 코드

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

const char keypad[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"};

void printWords(int number[], int curr_digit, char output[], int n){
    int i;
    if (curr_digit == n){
        cout << output << " ";
        return;
    }
    for (i = 0; i < strlen(keypad[number[curr_digit]]); i++){
        output[curr_digit] = keypad[number[curr_digit]][i];
        printWords(number, curr_digit + 1, output, n);
        if (number[curr_digit] == 0 || number[curr_digit] == 1)
            return;
    }
}

int main(void){
    int number[] = {6, 8, 7};
    cout << "생성된 문자 조합 : \n";
    int n = sizeof(number)/sizeof(number[0]);
    char result[n+1];
    result[n] = '\0';
    printWords(number, 0, result, n);
    return 0;
}

실행 결과

생성된 문자 조합 :
mtp mtq mtr mts mup muq mur mus mvp mvq mvr mvs ntp ntq ntr nts
nup nuq nur nus nvp nvq nvr nvs otp otq otr ots oup ouq our ous ovp
ovq ovr ovs

코드 설명 및 복잡도 분석

printWords 함수는 현재 처리 중인 자릿수(curr_digit)가 입력 길이(n)와 같아지면 지금까지 만든 문자열을 출력하고 재귀를 종료합니다. 그렇지 않으면 현재 자릿수에 해당하는 키패드 문자를 하나씩 output 배열에 대입한 뒤, 다음 자릿수를 처리하기 위해 자기 자신을 재귀적으로 호출합니다. 참고로 0과 1에는 대응하는 알파벳이 없으므로 해당 경우에는 반복을 중단합니다.

각 숫자가 최대 4개의 문자를 가질 수 있으므로 이 알고리즘의 시간 복잡도는 O(4^N)입니다(여기서 N은 입력 숫자열의 길이). 공간 복잡도는 결과를 저장하는 배열과 재귀 호출 스택을 포함하여 O(N)입니다.