LeetCode 17(Letter Combinations of a Phone Number, Python)

1. 문제 링크

• https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

2. 문제 설명

• 휴대폰 다이얼 버튼 2에는 abc, 3에는 def가 대응됨.
• digits=’23’이 주어지면 대응될 수 있는 모든 문자열을 모은 리스트 [’ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]를 반환하는 문제

3. 처음 풀이

• 다이얼과 문자를 대응시키는 {‘2’:’abc’, ‘3’:’def’, …, ‘9’:’wxyz’} 딕셔너리를 생성
• digit=’23’ 일 때 2에 해당하는 result = [’a’,’b’,’c’]가 만들어져있다고 하자.
• 주어진 digits을 앞에서부터 순회하는 for문을 돌리고
• 2 다음 3이 나오면 딕셔너리에서 ‘def’를 꺼냄.
• 이미 만들어진 result의 각 문자열 ‘a’, ‘b’, ‘c’와 꺼낸 ‘def’에 대해 이중 for문을 돌려 ‘a’+’d’ 부터 ‘c’+’f’까지 result 업데이트

 

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 각 숫자에 해당하는 문자들을 매핑한 딕셔너리
        numtoletter = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        
        # 초기 결과 리스트
        result = ['']

        # 입력된 숫자가 없으면 빈 리스트를 반환합니다.
        if digits == '':
            return []

        # 각 숫자에 대해 가능한 문자 조합을 생성
	# 예시) result = ['abc'], i=3 -> ad, ae, af, bd, be, bf, cd, ce, cf
        for i in digits:
            result = [x + y for x in result for y in numtoletter[i]]

        # 결과를 반환
        return result

4. 다른 풀이

• backtracking 이용한 풀이
• 재귀 함수에 현재까지 만들어진 문자열 조합과, 남은 digits 두 인자를 전달
• 시간 복잡도는 원래 풀이와 같고 실제 런타임도 비슷. 굳이 재귀적으로 푸는 장점이 있는 것 같지는 않음

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        # 각 숫자에 해당하는 문자들을 매핑한 딕셔너리
        phone_map = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mno',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }

        def backtrack(combination, next_digits):
            # 다음 숫자가 없을 때, 조합을 결과에 추가하고 종료합니다.
            if len(next_digits) == 0:
                output.append(combination)
            else:
                # 현재 숫자에 대한 각 문자에 대해 재귀적으로 진행합니다.
                for letter in phone_map[next_digits[0]]:
                    backtrack(combination + letter, next_digits[1:])

        output = []
        # 초기에는 빈 문자열과 입력된 숫자로 재귀적으로 진행합니다.
        backtrack("", digits)
        return output

5. 배운 점

• list comprehension 을 이중으로 쓸 수 있고, 원한다면 if문도 쓸 수 있음.

---

• backtracking(퇴각검색)이란?
  • GPT
    • 백트래킹(backtracking)은 해결책을 찾아가는 과정에서 가능한 한 많은 후보를 탐색하다가 현재의 후보가 해결책의 일부가 될 수 없다고 판단되면, 그 이전 단계로 돌아가 다른 후보를 탐색하는 알고리즘입니다.
  • 나무위키 백트래킹 - 나무위키 (namu.wiki)
  • 위키 퇴각검색 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)
  • 이 문제가 왜 백트래킹인 지는 모르겠음.(그냥 다 따지는데..?)
• backtracking의 사용
  • 재귀함수와 사용되는 경우가 많으며
  • 후보 선택 → 다음 단계 진행 → 조건 확인 → 해결 or 이전 단계로 돌아가기 의 반복
  • 가지치기를 하여 모든 경우를 따지는 깊이 우선 탐색을 하며, 절대로 답이 될 수 없는 경우임을 판단하면 그 이전 단계로 돌아가는 것이 backtracking의 예시
• 대표적인 문제
  • n-qeen 문제, n*n 격자에 n개의 퀸을 놓는데, 같은 세로, 가로, 대각선에 퀸이 동시에 있으면 안됨.
  • n개의 퀸을 모두 가능한 곳에 놓아보고 따지면 오래걸림
  • 따라서 하나의 퀸을 놓을 때마다 조건을 만족하는 지 따져보고, 해가 될 수 없다면 그 이전 퀸을 다음 칸에 놓고 계속해서 탐색.