이번에 살펴볼 문제는 제가 실제로 Facebook에서 인터뷰를 보면서 풀었던 문제입니다. 그때 당시에는 당황에서 잘 풀지 못했던 기억이 나네요. Recursive와 Iterative의 기념을 정확히 이해하고 적재적소에 활용하는 능력이 많이 부족했던 것 같습니다 ㅠ.ㅠ 여러분들도 미리미리 연습을 통해 뇌를 깨워놓으시길 :)

문제는 다음과 같습니다.

우리가 사용하는 전화번호 다이얼에는 할당된 알파벳들이 있습니다.
전화번호가 주어졌을 때, 이 알파벳들로 만들 수 있는 모든 문자열들을 출력하시오.


언뜻 보기에는 간단해 보이긴 하는데, 막상 짧은 인터뷰 시간에 질문을 받으니, 그리고 명확하게 구조를 이해하고 있지 않으면 버그가 많은(buggy) 코드를 짜게 되고.. 결국 떨어지겠죠? ^^

가급적 일반적으로 권장되는 방식인 Iterative 방식을 이용해서 짜도록 하겠습니다. Iterative 방식을 사용할 때 대표적으로 많이 쓰는 trick은 Queue를 이용한 계속된 반복입니다. 제가 이번에 사용한 방식은, k번째 번호까지 사용해 만들어진 문자열들에 k+1번째 번호가 올 수 있는 알파벳들을 각각 붙이는 것입니다. 예를 들면, 2에 의해 A, B, C라는 문자열이 생성되었으면, 3이라는 숫자가 왔을 때는 각각 AD, AE, AF, BD, BE, BF, CD, CE, CF 이렇게 확장시켜 나가는 것이죠. 아래의 코드를 보면서 이해해봅시다~

def generateAlpha(numbers):
	#먼저 각 번호에 해당하는 알파벳들을 dictionary 구조에 저장합니다.
    numToAlpha = {'2': 'ABC', '3': 'DEF', '4': 'GHI', '5': 'JKL', '6':'MNO', '7':'PQRS', '8':'TUV', '9':'WXYZ'}

    #일단 번호가 없으면 None을 리턴합니다.
    if len(numbers) == 0:
        return None

    #여기서부터 중요한 trick이 시작됩니다.
    queue = [''] #일단은 queue에 빈 문자열로 시작합니다.(string 연산을 위한 트릭입니다.)
    #각 번호의 숫자마다 루프를 돌면서
    for num in numbers:
        if num == '1': #1은 해당 알파벳이 없으므로 패스
            continue

        length = len(queue) # 현재까지 저장된 문자열의 개수를 받아옵니다.
        # 그 문자열의 개수만큼 반복하면서
        for i in range(length):
            string = queue.pop(0) #queue에서 각각 문자열을 하나씩 꺼내서
            for ch in numToAlpha[num]: #해당 숫자가 가능한 모든 알파벳들을 붙여서 다시 queue에 넣어줍니다.
                queue.append(string + ch)
    return queue

이제 실제로 결과가 잘 나오는지 확인해 봅시다 :)

>>> generateAlpha('123')
['AD', 'AE', 'AF', 'BD', 'BE', 'BF', 'CD', 'CE', 'CF']
>>> generateAlpha('94')
['WG', 'WH', 'WI', 'XG', 'XH', 'XI', 'YG', 'YH', 'YI', 'ZG', 'ZH', 'ZI']

너무 긴것은 여기서 확인시켜드리지 못한 점 죄송하게 생각합니다 :( 그래도 직접 여러분들 컴퓨터로 확인해 보시면 좋을 것 같네요 :) Iterative 알고리즘을 구현할 때 Queue의 활용과 중요성! 명심하시고 많이 연습해 보세요~