Computer >> 컴퓨터 >  >> 프로그래밍 >> C 프로그래밍

C/C++로 전화 번호에 대응하는 모든 문자열 조합 출력하기

문제 개요

주어진 전화 번호에 대해, 일반적인 전화기 자판 규칙에 따라 해당 번호를 누를 때 만들어낼 수 있는 모든 문자열 조합을 화면에 출력하는 프로그램을 C/C++로 작성하는 방법을 알아보겠습니다.

전화 자판 매핑 규칙

  • 숫자 2 → A, B, C 중 하나
  • 숫자 3 → D, E, F 중 하나
  • 숫자 4 → G, H, I 중 하나
  • 숫자 5 → J, K, L 중 하나
  • 숫자 6 → M, N, O 중 하나
  • 숫자 7 → P, Q, R, S 중 하나
  • 숫자 8 → T, U, V 중 하나
  • 숫자 9 → W, X, Y, Z 중 하나
  • 숫자 1과 0은 각각 1, 0으로만 표현됩니다

예를 들어 주어진 전화 번호가 89라면, 프로그램은 다음과 같이 출력해야 합니다.

TW, TX, TY, TZ, UW, UX, UY, UZ, VW, VX, VY, VZ

C 언어 구현 코드

아래 코드는 재귀 호출을 이용해 모든 조합을 생성합니다. 각 자릿수에 대응하는 후보 문자를 하나씩 넣어 보고, 모든 자릿수가 채워지면 완성된 문자열을 출력한 뒤 다음 후보 문자로 넘어가는 방식입니다.

#include <stdio.h>
#include <string.h>

// TableHash[i]에는 전화기에서 숫자 i에 해당하는 모든 문자가 저장됩니다.
const char TableHash[10][5] = {
    "", "", "ABC", "DEF", "GHI",
    "JKL", "MNO", "PQRS", "TUV", "WXYZ"
};

// 입력 숫자 배열 number1[](크기 n1)로부터 만들 수 있는
// 모든 단어를 출력하는 재귀 함수입니다.
void UtilWordsPrint(int number1[], int curr_digit1, char output1[], int n1) {
    int i;
    // 기저 사례(base case): 현재 출력 단어가 완성된 경우
    if (curr_digit1 == n1) {
        printf("%s ", output1);
        return;
    }
    // 현재 자릿수에 대해 가능한 모든 문자를 시도하고,
    // 나머지 자릿수에 대해 재귀 호출합니다.
    for (i = 0; i < strlen(TableHash[number1[curr_digit1]]); i++) {
        output1[curr_digit1] = TableHash[number1[curr_digit1]][i];
        UtilWordsPrint(number1, curr_digit1 + 1, output1, n1);
        if (number1[curr_digit1] == 0 || number1[curr_digit1] == 1)
            return;
    }
}

// UtilWordsPrint()의 래퍼(wrapper) 함수.
// output1 배열을 생성한 뒤 UtilWordsPrint()를 호출합니다.
void printWords(int number1[], int n1) {
    char result1[n1 + 1];
    result1[n1] = '\0';
    UtilWordsPrint(number1, 0, result1, n1);
}

// 드라이버(Driver) 프로그램
int main(void) {
    int number1[] = {2, 3, 4};
    int n1 = sizeof(number1) / sizeof(number1[0]);
    printWords(number1, n1);
    return 0;
}

실행 결과

입력이 {2, 3, 4}일 때 위 프로그램의 출력 결과는 다음과 같습니다.

ADG ADH ADI AEG AEH AEI AFG AFH AFI BDG BDH BDI BEG BEH BEI BFG BFH BFI CDG CDH CDI CEG CEH CEI CFG CFH CFI

시간 복잡도

위 코드의 시간 복잡도는 O(4n)입니다. 여기서 n은 입력 번호의 자릿수를 의미합니다. 각 자릿수마다 최대 4개의 문자(예: 7의 PQRS, 9의 WXYZ)를 가질 수 있으므로, 만들어질 수 있는 조합의 총 개수는 최대 4의 n제곱이 됩니다. 참고로 0과 1처럼 대응되는 문자가 없는 숫자는 그대로 유지되며 추가 분기가 발생하지 않습니다.