๋ฌธ์ ๋งํฌ
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
๋ฌธ์ ์ค๋ช
๊ฐ๋จํ ๋ฐฑํธ๋ํน ๋ฌธ์
๋ฌธ์ ํด๊ฒฐ๊ณผ์
์ด๋ฒ ๋ฌธ์ ๋ ์ด๋ ต์ง๋ ์์๊ณ ํ ์คํธ์ผ์ด์ค๋ ์ ๋ถ ํต๊ณผ๋ฅผ ํ์ง๋ง ๋ฌธ์ ๋ฅผ ํ๊ธฐ์ํ ์ ๊ทผ์ ์กฐ๊ธ์ ์ด์ํ๊ฒ ํ ๋ถ๋ถ์ด ์์๊ธฐ์ ๊ทธ ๋ถ๋ถ์ ์ง๊ณ ๋์ด๊ฐ๊ณ ์ ํ๋ค.
letters = [[],[],['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']]
class Solution:
def backtracking(arr,ans, digits,results):
if len(ans) == len(digits):
print(ans)
if ans not in results:
results.append(ans)
return
for i in range(len(arr)):
if arr[i] in letters[int(digits[len(ans)])]:
Solution.backtracking(arr, ans+arr[i], digits,results)
def letterCombinations(self, digits: str) -> List[str]:
arr = []
for i in range(len(digits)):
index = int(digits[i])
for j in range(len(letters[index])):
arr.append(letters[index][j])
results = []
Solution.backtracking(arr,'',digits, results)
print(arr)
if len(results) == 1 and results[0] == "":
return []
# return list(set(results))
return results
๋๋ arr์ด๋ผ๋ ๋ฐฐ์ด์ ์ฌ์ฉํ ์ ์๋ ๋ชจ๋ letter๋ฅผ ๋ฃ์๋๋ฐ ์ด๋ ๊ฒ ํ๋ ๋์ค์ ์ค๋ณต๋ ๋ถ๋ถ์ ๋ฐ๋ก ์ฒ๋ฆฌํด์ค์ผ ํ๋ ๋ถํธํจ์ด ์์๋ค. letters๋ผ๋ ๋ฐฐ์ด์ backtracking์ด๋ผ๋ ํจ์์์ ์ฌ์ฉํ๊ณ ๊ทธ๊ฑธ๋ก for๋ฌธ์ ๋๋ฉด๋๋๋ฐ ๊ตณ์ด arr์ ๋ง๋ค์ด ์ค๊ฒ์ด๋ค.. (์ด๋ฒ ๋ฌธ์ ๋ฅผ ํ๋ฉด์ ์ ๋ง ์๊ณ ๋ฆฌ์ฆ์ ์ค์์ฑ์ ๊นจ๋ฌ์๋ค. ๋จ์ ์ฝํ ๋ฅผ ํต๊ณผํ๊ธฐ ์ํด์๊ฐ ์๋๋ผ ์ฝํ ๋ฅผ ๊ณต๋ถํ๋ฉฐ ์ฝ๋๋ฅผ ์์ง๊ธฐ ์ํ ํ๋ จ์ ํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.)
๋ฌธ์ ๋ฅผ ํ๊ณ ์ฐธ๊ณ ํ ๋ต
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
digit_to_letters = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz',
}
def backtrack(idx, comb):
if idx == len(digits):
res.append(comb[:])
return
for letter in digit_to_letters[digits[idx]]:
backtrack(idx + 1, comb + letter)
res = []
backtrack(0, "")
return res
์ ํ์ด๋ฅผ ๋ณด๋ฉด ์ ์๋๋ก ๊น๋ํ๊ฒ ์ฝ๋ฉ์ ํ ๊ฒ์ ์ ์ ์๋ค. ์๋ฃ๊ตฌ์กฐ๋ฅผ ๊ฐ์ฒด๋ก ํ๋ ๊ตณ์ด ์ธ๋ฑ์ค๋ฅผ ์ซ์๋ก ๋ฐ๊ฟ์ค ํ์๋ ์๋ค. ์ด ์ฝ๋๋ฅผ ๋ณด๊ณ ๋ง์ด ๋ฐฐ์ ๋ค.
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค ๋ธ๋ฃจํ ํฌ์ค/๋ฐฑํธ๋ํน/๋นํธ๋ง์คํน] ๊ฐ๋ฅด์นจ (0) | 2024.05.07 |
---|---|
[๋ฐฑ์ค ๊ตฌํ/๋ฌธ์์ด] 1148 ๋จ์ด ๋ง๋ค๊ธฐ (0) | 2024.05.05 |
[๋ฐฑ์ค ์ ๋ ฌ] ๊ฐ์์ค ๋ฐฐ์ (0) | 2024.04.22 |
[PCCP ๊ธฐ์ถ๋ฌธ์ ] 1๋ฒ / ๋ถ๋ ๊ฐ๊ธฐ (์๋ฐ์คํฌ๋ฆฝํธ ํ์ด) (0) | 2023.12.09 |
[์ฝ๋ํธ๋ฆฌ] ๊ฒน์ณ์ง์ง ์๋ ๋ ์ง์ฌ๊ฐํ ํ์ด (2) | 2023.11.07 |