파이썬으로 전화 자판 숫자의 모든 문자 조합 구하기

2부터 9까지의 숫자로만 이루어진 문자열이 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 해당 숫자 조합이 나타낼 수 있는 모든 가능한 문자 조합을 반환하는 것입니다. 아래는 일반적인 전화기 자판을 기준으로 한 숫자와 문자의 매핑 표입니다. 참고로 숫자 1은 어떤 문자에도 매핑되지 않습니다.

문제 예시

예를 들어 입력 문자열이 "23"이라면, 각 숫자에 대응하는 문자들을 조합하여 다음과 같은 결과를 얻을 수 있습니다.

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

풀이 접근 방법

이 문제는 재귀(백트래킹) 기법을 활용하면 깔끔하게 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 문제를 재귀적으로 해결하기 위한 solve 메서드를 정의합니다.
• solve 메서드는 digits(숫자 문자열), characters(매핑 딕셔너리), result(결과 리스트), current_string(현재까지 만든 문자열), current_level(현재 탐색 위치)을 인자로 받습니다.
• 현재 레벨(current_level)이 숫자 문자열의 길이와 같아지면, 지금까지 만든 문자열을 결과 리스트에 추가하고 재귀를 종료합니다.
• 그렇지 않다면, 현재 레벨의 숫자에 매핑된 각 문자 i에 대해 다음을 수행합니다.
  • solve(digits, characters, result, current_string + i, current_level + 1)을 호출하여 다음 자릿수를 탐색합니다.
• 실제 실행 함수는 다음과 같이 동작합니다.
• 입력 문자열의 길이가 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("37"))

입력

"37"

출력

["dp","dq","dr","ds","ep","eq","er","es","fp","fq","fr","fs"]

동작 원리 정리

위 코드는 전형적인 DFS(깊이 우선 탐색) 방식의 백트래킹 알고리즘입니다. 첫 번째 숫자에 해당하는 문자부터 차례대로 붙여 가며 다음 자릿수로 진행하고, 모든 자릿수를 채웠을 때 하나의 완성된 조합을 결과에 저장합니다. 시간 복잡도는 각 숫자에 매핑된 문자 개수(3 또는 4)의 곱에 비례하며, 입력 길이가 n일 때 최대 O(4ⁿ)의 조합이 생성될 수 있습니다.