[리트코드/leetcode/python] 17. Letter Combinations of a Phone Number

이미지를 누르면 문제 링크를 보실 수 있습니다

문제 설명부터 해보도록 하겠습니다.

digits 이라는 숫자 문자열을 입력값으로 받는데요, 각 숫자 키패드에 해당하는 알파벳 문자열로 만들 수 있는 모든 문자열의 리스트를 출력하는 문제입니다.

예시 1을 보면, digits은 "23"으로 주어졌고, 각 숫자인 "2"에는 "abc"의 알파벳이, "3"에는  "def"의 알파벳이 주어져있습니다. 때문에, "23"으로 만들 수 있는 알파벳 문자열은 "ad"부터 "cf"까지 총 9가지가 될 수 있는 것을 알 수 있습니다.

여기서 캐치해야 할 점은 만들 수 있는 알파벳 문자열의 길이는 digits의 길이와 같을 수 밖에 없다는 점입니다. 흡사 순열과 조합 문제로 이해될 수 있는데, 보통 알고리즘 문제에서는 combination을 사용하거나 product, permutation 등의 라이브러리를 사용하도록 문제를 내지는 않을 것입니다. 

 

이렇게 모든 조합을 찾는 문제는 "백트래킹" 알고리즘으로 접근해볼 필요가 있습니다.

그림으로 표현하자면 아래와 같습니다.

백트래킹

for문을 여러번 사용하거나 라이브러리를 통해 순열,조합을 사용한다고 싶으면, 백트래킹 유형이라고 의심한번 해봅시다!

backtracking도 재귀를 쓰기 때문에 탈출조건이 필요한 것을 잊지말고 코드를 한 번 짜봅시다.

완성된 코드는 아래와 같습니다.

class Solution(object):
    def letterCombinations(self, digits):

        answer = []

        digitToChar = {
            "2" : "abc",
            "3" : "def",
            "4" : "ghi",
            "5" : "jkl",
            "6" : "mno",
            "7" : "pqrs",
            "8" : "tuv",
            "9" : "wxyz"}

        
        def backtracking(i,curStr):

            if len(digits) == len(curStr):
                answer.append(curStr)
                return 
            
            for alphabet in digitToChar[digits[i]]:
                backtracking(i+1, curStr + alphabet)
            
        if digits:
            backtracking(0,"")
        
        return answer

먼저 전화기에 있는 각 숫자에 대한 문자를 연결시켜주는 해시 형태, 즉 딕셔너리를 만들어줬습니다.

이제 backtracking을 해야 하는데, 탈출조건 즉, 위 그림에서 따져보면 다시 위로 올라가는 조건은 현재의 string과 digits의 길이가 같으면 됩니다. 답은 digits보다 길어질 수 없으니까요.

 

그 외에 계속 backtracking함수를 재귀적으로 타면 되는데, 인덱스를 1 증가시켜주는 작업과 alphabet을 하나씩 붙여주는 작업이 필요합니다. 해당 코드를 하나하나 밟아가보면 아래와 같은 그림처럼 로직이 흘러가는 것을 알 수 있습니다.

digits이 '23'일 때, 로직을 그림으로 표현

말 그대로 "back" "Tracking"입니다. return 을 만나면 answer에 curStr을 추가해주면서, 다시 재귀를 탔던 지점으로 돌아가는 셈이죠.

 

아 그리고, 마지막에 if digits:을 해준 이유는 저 작업을 안해주면, digits이 빈 문자열일 때, answer는 [""]와 같은 객체를 반환하므로, 이를 방지하고자 digits이 빈 객체가 아닐 때만 backtracking을 해주는 로직을 만들었습니다.

 

많은 for문을 쓰거나 순열과 조합 문제인가라는 의심이 들 때는 , BackTracking을 해봅시다. 이번 문제를 통해 백트래킹을 하는 문제에 대해 배워보는 시간이었습니다.

이상으로 Backtracking과 관련한 17. Letter Combinations of a Phone Number 문제를 정리해봤습니다.