문제) 전화기의 몇몇 번호에는 알파벳이 할당되어 있다. 전화 번호가 주어지면 가능한 알파벳 조합을 모두 출력하라. 단, 0, 1번에는 알파벳이 할당되어 있지 않고, 2~8번에 각 3개씩 알파벳이 할당되어 있다고 하자. 단 Q, Z는 할당되어 있지 않다.
일종의 순열 출력 문제라고 할 수 있다. 예를 들어 번호가 123번이면 1AD, 1AE, 1AF, 1BD, 1BE, 1BF, 1CD, 1CE, 1CF와 같이 9가지가 나온다. 기본적으로 재귀(recursion)를 사용하는 것이 생각하기 쉽다. 여기에서는 재귀 이외에도 반복(iteration)을 사용하는 것도 생각해보자.
먼저 기본적으로 세팅하는 부분이다. 특별한 것은 없다.
#include <iostream>
using namespace std;
#define MAX_LENGTH_OF_PHONE_NUMBER 7
// 0, 1 are not translated into alphabets.
string numStr[8] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PRS", "TUV", "WXY"};
void printTelephoneWords(char*, char*, int);
void printTelephoneWordsNonRec(char*, char*);
int main() {
char phone[MAX_LENGTH_OF_PHONE_NUMBER+1]; // original phone number
char tphone[MAX_LENGTH_OF_PHONE_NUMBER+1]; // translated words
while (true) {
memset(tphone, 0x00, MAX_LENGTH_OF_PHONE_NUMBER+1);
cin >> phone;
if (cin.eof())
break;
cout << "With Recursion" << endl;
printTelephoneWords(phone, tphone, 0);
cout << "With Iteration" << endl;
printTelephoneWordsNonRec(phone, tphone);
}
return 0;
}다음은 재귀를 사용해서 구현한 부분이다. 이 부분은 DFS(Depth First Search)처럼 생각하면 된다.
void printTelephoneWords(char *phone, char *tphone, int index) {
if (index == strlen(phone)) {
cout << tphone << endl;
return;
}
for (int j = 0; j < 3; j++) {
if (phone[index] == '0' || phone[index] == '1')
tphone[index] = phone[index];
else
tphone[index] = numStr[phone[index]-'2'].at(j);
printTelephoneWords(phone, tphone, index+1);
if (phone[index] == '0' || phone[index] == '1')
return;
}
}다음은 재귀를 사용하지 않고 반복을 사용하는 부분이다. 모든 재귀는 반복으로 구현할 수 있다고 들었던 것 같다. 쉽진 않다.
void printTelephoneWordsNonRec(char *phone, char *tphone) {
int len = strlen(phone);
for (int i = 0; i < len; i++) {
if (phone[i] == '0' || phone[i] == '1')
tphone[i] = phone[i];
else
tphone[i] = numStr[phone[i]-'2'].at(0);
}
while (true) {
cout << tphone << endl;
for (int i = len - 1; i >= 0; i--) {
if (tphone[i] == '0' || tphone[i] == '1') {
tphone[i] = phone[i];
} else if (tphone[i] == numStr[phone[i]-'2'].at(2)) {
tphone[i] = numStr[phone[i]-'2'].at(0);
} else if (tphone[i] == numStr[phone[i]-'2'].at(0)) {
tphone[i] = numStr[phone[i]-'2'].at(1);
break;
} else if (tphone[i] == numStr[phone[i]-'2'].at(1)) {
tphone[i] = numStr[phone[i]-'2'].at(2);
break;
}
if (i == 0) return;
}
}
}
