🚥 문제 🚥
Top Interview 150 중
17. Letter Combinations of a Phone Number
🍿 난이도 : 리트코드 기준 Medium
🚧 알고리즘 : 백트랙킹 (backtracking)
🚦 풀이1 🚦
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
letter = {"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"]}
zipping = []
for num in digits:
# print(letter[num])
if len(zipping):
newzip = []
for i in zipping:
for j in letter[num]:
newzip.append(i + j)
zipping = newzip
else:
zipping = letter[num]
return (zipping)🚧 python의 list, dictionary 자료구조를 사용했다.
🚧 백트랙킹 문제인걸 알았지만 바로 어떻게 구현할 지 생각이 나지 않아서 우선 brute force로 풀어봤다.
🏗 letter : 문제에서 제시한 번호판대로 만들어 둔 dictionary.
🏗 zipping : 최종 결과값을 담는 배열
🏗 new zip : 한번 순환할 때 임시로 값을 저장하는 배열
🚧 digits에 들어있는 번호와 같은 번호를 letter에서 찾아서 해당하는 알파벳 리스트를 하나씩 돌아가면서 진행한다.
🚧 만약, zipping에 담겨있는 값이 없다면, 1번째 순회이므로, letter에서 digits[0]에 해당하는 알파벳 리스트를 찾아서 zipping에 넣어준다.
🚧 만약, zipping에 담겨있는 값이 있다면, 2번째 순회이므로, 앞서 넣어둔 zipping의 값들과 현재 digits에 해당하는 알파벳 리스트를 1:1로 매칭해서 newzip 리스트에 담는다. 한번의 순회가 끝나면 새로 만든 newzip의 값으로 zipping의 값들을 대체한다.
풀이 결과
나쁘지 않은 결과였지만, 백트랙킹 방식으로도 풀어보고 싶어서 다시 문제를 풀었다.
🚦 풀이2 🚦
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if (digits == ""):
return []
letter = {"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"]}
if (len(digits) == 1):
return letter[digits]
beforelist = self.letterCombinations(digits[:-1])
newlist = [i+j for i in beforelist for j in letter[digits[-1]]]
return newlist🚧 이번에는 재귀방식으로 풀었다. 백트랙킹 알고리즘은 경우의 수를 나무가지처럼 뻗어나가다가 조건에 맞지 않으면 거기서 다시 나무가지의 분기점으로 돌아와서 다른방향으로 진행하는 방식이라고 알고 있었는데, 문득 재귀로 했던 것 같은 생각이 스쳤다. 재귀를 도입해보기로 했다.
🏗 letter : 문제에서 제시한 번호판대로 만들어 둔 dictionary.
🏗 beforelist : 재귀함수에서 돌려받은 리스트
🏗 newlist : return할 리스트
🚧 digits기준으로 뒤에 있는 알파벳부터 하나씩 보면서 재귀를 진행한다. 가장 깊은 단계의 재귀에서는 맨 앞의 1개의 digit을 보고, 해당하는 알파벳 리스트를 담아서 돌려준다. 중간 단계들에서는 앞서 받은 beforelist와 현재 digit에 맞는 알파벳리스트를 1:1매칭해서 새로운 newlist에 담아준다. 이때는 2중 for문 대신 list comprehension을 사용해봤다.
🚧 leetcode에서 제공해주는 solution class 안에 있는 함수를 사용할 때는 self.letterCombinations(digits[:-1]) 이런 식으로 작성해줘야한다는 것을 처음알았다. 두둥탁. 이와 관련해서 찾아본 참고질문 -> leetcode general discussion
풀이 결과
와 메모리 기준에서 90퍼 달성해본 건 처음이다.
백트랙킹 방식에 가까워진듯하지만 여전히 백트랙킹 방식은 아닌 것 같다고 느꼈다. 어디서? 가지치기가 없다는 점에서.
가지치기는 효율을 위해 도입한 백트랙킹 알고리즘의 핵심개념이다.
앞서 말했던 백트랙킹 알고리즘에 대한 설명 백트랙킹 알고리즘은 경우의 수를 나무가지처럼 뻗어나가다가 조건에 맞지 않으면 거기서 다시 나무가지의 분기점으로 돌아와서 다른방향으로 진행하는 방식 중에서 "조건에 맞지 않으면"에 해당한다.
그래서 가지치기에 대한 힌트를 얻었다. : 앞에부터 digit을 보세요 :
🚦 풀이3 🚦
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if (digits == ""):
return []
letter = {"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"]}
if (len(digits) == 1):
return letter[digits]
result = []
def backtracking(res : string):
if (len(res) == len(digits)):
result.append(res)
return
for i in letter[digits[len(res)]]:
backtracking(res + i)
backtracking("")
return result🚧 드디어 백트랙킹 방식의 약 90퍼쯤 온 것 같다. 주로 백트랙킹 알고리즘을 dfs, bfs등 트리에 대한 알고리즘으로 선택을 했었기에 string에 대한 순회방식과 함께 사용하는 게 어색했다.
🚧 비어있는 digits와 하나의 number에 대한 리스트를 리턴하는 방식은 이전 풀이와 같다.
🏗 result : 결과를 return해줄 리스트
🏗 res : 백트랙킹 함수에서 사용하는 하나의 문자열.
🚧 이번에는 힌트에 따라서 뒤부터가 아닌 앞부터 뜯어보기로 했다.
🚧 그리고 이전의 재귀함수에서는 리스트 자체를 리턴해줬는데, 백트랙킹함수에서는 함수 바깥에 리턴해줄 리스트 하나를 만들어두고, 함수 내부에서는 하나의 string에 대해서만 추적했다.
그래서 이전 풀이의 재귀함수에서는 digit 1개당 1번의 재귀를 호출했지만, backtracking함수에서는 string마다 1개의 char에 대해서 1번의 재귀함수를 호출했기 때문에, depth는 비슷하지만 재귀함수를 호출하는 횟수자체가 달라진다.
그림으로 표현하면 이렇다.
그래서 풀이과정에서, backtracking("") backtracking("ad") 이런식으로 전달한다.
🚧 하나의 string이 완성되었는지, 아닌지를 판단하는 기준은 digits의 길이와 같은지 아닌지이다. 재귀를 들어가기전에 맨 앞의 digit에 대해서 문자열을 세팅하고, 재귀에 들어가서 두번째 digit에 대해서 세팅하고, 알파벳 리스트의 길이만큼 다시 backtracking을 호출한다.
풀이 결과
결과적으로 런타임 실행속도에서 많이 좋아졌다.
그리고, 스트링을 재귀하는 방식과 리스트를 재귀하는 방식을 비교하는 그림을 그리다보니 사실상 리스트를 재귀하는 방식은 재귀함수를 썼을 뿐이고 brute force라는 걸 깨달아버렸다. 크흡...
아무튼 오늘도 이렇게 알고리즘 하나 풀기 완료 ⭐️
