[파이썬 알고리즘 인터뷰][그래프] 전화 번호 문자 조합

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

2~9 범위의 문자열에 대해 가능한 모든 문자 출력

 

책에서 구현된 코드

def letterCombinations(digits: str) -> list[str]:
    def dfs(index, path):
        if len(path) == len(digits):
        result.append(path)
        return
        
        for i in range(idex, len(digits)):
            for i in dic[digits[i]]:
                dfs(i + 1, path + j)
    
    if not digits:
        return []
    
    dic = {"2": "abc",
           "3": "def",
           "4": "ghi",
           "5": "jkl",
           "6": "mno",
           "7": "pqrs",
           "8": "tuv",
           "9": "wxyz"}
    result = []
    dfs(0, "")
    
    return result

 

기억해야할 기법

• 재귀 함수의 인자로 str을 줘도 느리지 않음
  • 재귀 함수가 호출될 때마다 저장되는 str에 현재 char를 붙임
  • depth가 마지막이면 현재까지 str을 result에 append

 

내가 구현한 코드

def letterCombinations(digits: str) -> list[str]:
    dic = {"2": "abc",
           "3": "def",
           "4": "ghi",
           "5": "jkl",
           "6": "mno",
           "7": "pqrs",
           "8": "tuv",
           "9": "wxyz"}
    tmp_str = []
    result = []

    def dfs(depth: int):
        for c in dic[digits[depth]]:
            tmp_str.append(c)
            if depth == len(digits) - 1:
                result.append(''.join(tmp_str))
            else:
                dfs(depth+1)
            tmp_str.pop()
    if len(digits):
        dfs(0)

    return result

• 재귀함수마다 str에 연산이 일어나는게 비효율적이라 생각했다
• list에 char를 append 후 마지막 depth에서만 string으로 조합해주는게 더 빠를거라 생각했음
  - list의 append / pop은 O(1)이고, list는 가변객체라 값만 바꾸면 되니까
  - string 불변객체로 매번 연산이 일어날 때마다 새로운 객체를 생성해야하니까
  - 문제는 ''.join으로 일어나는 list -> string의 오버헤드인데, 그래도 마지막 depth에서만 일어남
• 1번씩만 제출했지만, 그래도 책에서 구현한 알고리즘이 더 빠름