파이썬으로 전화 키패드 숫자에서 만들 수 있는 모든 문자 조합 찾기

2부터 9까지의 숫자로 이루어진 문자열이 주어졌을 때, 해당 숫자들이 만들어낼 수 있는 모든 문자 조합을 찾는 문제를 생각해 봅시다. 각 숫자에 대응되는 문자 매핑은 일반적인 전화기 키패드와 동일하며, 아래 표와 같습니다. 참고로 숫자 1은 어떤 문자에도 매핑되지 않습니다.

예를 들어 입력 문자열이 "49"라면, 숫자 4는 g, h, i에 대응하고 숫자 9는 w, x, y, z에 대응하므로 가능한 결과는 다음과 같습니다.

['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']

해결 접근 방법

이 문제는 재귀(백트래킹) 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 문제를 재귀적으로 풀기 위한 solve 메서드를 정의합니다.
• solve 메서드는 digits(숫자 문자열), characters(매핑 딕셔너리), result(결과 리스트), current_string(현재까지 만든 문자열), current_level(현재 탐색 중인 자릿수)을 인자로 받습니다.
• current_level이 digits의 길이와 같아지면, 지금까지 만든 current_string을 result에 추가하고 재귀를 종료합니다.
• 그렇지 않으면 characters[digits[current_level]]에 속한 모든 문자 i에 대해 solve(digits, characters, result, current_string + i, current_level + 1)을 호출합니다.

실제 실행 함수의 동작 흐름은 다음과 같습니다.

• digits의 길이가 0이면 빈 리스트를 반환합니다.
• 숫자와 대응 문자를 담은 매핑 딕셔너리를 정의합니다.
• result를 빈 리스트로 초기화합니다.
• solve(digits, characters, result, "", 0)을 호출하여 결과를 생성합니다.

구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

class Solution(object):
   def letterCombinations(self, digits):
      if len(digits) == 0:
         return []

      characters = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
      result = []
      self.solve(digits,characters,result)
      return result

   def solve(self, digits, characters, result, current_string="",current_level = 0):
      if current_level == len(digits):
         result.append(current_string)
         return
      for i in characters[int(digits[current_level])]:
         self.solve(digits,characters,result,current_string+i,current_level+1)

ob1 = Solution()
print(ob1.letterCombinations("49"))

입력

"49"

출력

['gw', 'gx', 'gy', 'gz', 'hw', 'hx', 'hy', 'hz', 'iw', 'ix', 'iy', 'iz']

시간 복잡도 분석

각 숫자마다 최대 4개의 문자가 대응될 수 있으므로, 입력 길이가 n일 때 시간 복잡도는 O(4^n)입니다. 공간 복잡도 역시 결과를 저장하는 데 O(4^n)이 필요합니다. 이러한 백트래킹 기법은 조합을 생성하는 전형적인 패턴이므로, N-Queens나 부분 집합 생성 같은 다른 재귀 문제에도 동일한 사고방식을 적용할 수 있습니다.