17. Letter Combinations of a Phone Number

입력값으로 번호를 받으면, 그로 인해 만들어질 수 있는 알파벳의 조합을 모두 출력하는 문제이다.

모든 경우의 수를 만들어야 하므로, 백트래킹 알고리즘이라는 것을 알 수 있다.

 

알파벳을 모두 배열에 넣기 귀찮아서, 아스키코드값과 번호와의 방정식을 세워서 하기로 결심했다.

 

-> 7,9번이 알파벳이 4개인 것을 간과해서 이 방법은 결국 난잡하게 되었다.

 

문제 해결 방식

1. 숫자를 앞부분부터 탐색

2. 숫자에 알맞는 알파벳을 임시문자열 공간에 더하고 다음 숫자로 넘어가는 재귀함수를 호출
3. 만약, 숫자를 모두 탐색했다면, 임시문자열의 문자열을 해답 배열에 넣는다.

 

문제에서 얻어갈 점

1. DFS와 백트래킹의 차이점, 그리고 이 문제가 단순 재귀문제가 아니고 백트래킹이라는 것. (알파벳을 추가하여 재귀함수를 호출하고 문자를 지우고 다시 되돌아가서 다른 문자를 채운 재귀함수를 호출하기 때문)
2. Dictionary를 활용한 코드에 대해서도 생각해볼 것
3. 함수의 self에 대해 다시 잘 공부해보기 -> recur(self,i,st)가 아닌 recur(i,st)라는 점

3) self 이해하기 - 파이썬으로 배우는 알고리즘 트레이딩 (개정판-2쇄) (wikidocs.net)

위키독스

나의 코드

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        answer = []
        if len(digits) == 0:
            return answer
        def recur(i,st):
            if i == len(digits):
                answer.append(st)
            else:
                k = int(digits[i])
                if k <= 6:
                    recur(i+1, st + chr(3*k+91))
                    recur(i+1, st + chr(3*k+92))
                    recur(i+1, st + chr(3*k+93))
                elif k == 7:
                    recur(i+1, st + chr(112))
                    recur(i+1, st + chr(113))
                    recur(i+1, st + chr(114))
                    recur(i+1, st + chr(115))
                elif k == 8:
                    recur(i+1, st + chr(116))
                    recur(i+1, st + chr(117))
                    recur(i+1, st + chr(118))
                elif k == 9:
                    recur(i+1, st + chr(119))
                    recur(i+1, st + chr(120))
                    recur(i+1, st + chr(121))
                    recur(i+1, st + chr(122))
                    

        recur(0,"")    
        return answer

 

Leetcode 솔루션에 있는 Dictionary를 활용한 코드

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
                
        def backtrack(combination, next_digits):
            # if there is no more digits to check
            if len(next_digits) == 0:
                # the combination is done
                output.append(combination)
            # if there are still digits to check
            else:
                # iterate over all letters which map 
                # the next available digit
                for letter in phone[next_digits[0]]: #숫자를 key로 활용
                    # append the current letter to the combination
                    # and proceed to the next digits
                    backtrack(combination + letter, next_digits[1:])
                    
        output = []
        if digits:
            backtrack("", digits)
        return output