๐ ๋ชฉ์ฐจ
๐ค ๋ฌธ์ : Generate Parentheses | LeetCode 794
๋ฌธ์ : https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/
Stack์ ํ์ฉํ ๋จ๊ณจ๋ฌธ์ ์ค ํ๋์ธ ๊ดํธ๋ง๋ค๊ธฐ์ ๋๋ค.
n๊ฐ์ ์ด๋ฆฐ๊ดํธ, ๋ซํ๊ดํธ๋ฅผ ํ์ฉํ์ฌ ์ ๋ซํ ๊ดํธ๋ค์ ๋ง๋ค์ด ๋ฆฌ์คํธ๋ก ๋ฐํํ๋ฉด ๋ฉ๋๋ค.
์ ๋ซํ ๊ดํธ(?)
((())) [O] ()) [X] ์ฐ ๊ฒ ๋ณด๋ค ๋ ๋ง์ด ๋ซ์ ((()) [X] ํ๋๋ฅผ ๋ ๋ซ์ |
๐ก ํ์ด
1. ์ ๊ทผ - ์ ๋ซํ ๊ดํธ์ ์กฐ๊ฑด์?
((())) [O] ()) [X] ์ฐ ๊ฒ ๋ณด๋ค ๋ ๋ง์ด ๋ซ์ ((()) [X] ํ๋๋ฅผ ๋ ๋ซ์ |
์์ ๊ดํธ ์ผ์ด์ค๋ค์ ๋ณด๋ฉฐ ์ ๋ซํ ๊ดํธ์์ ๊ฐ์ฅ ๊ฐ๋จํ๊ฒ ํ๋จํ๋ ๋ฐฉ๋ฒ์ ๋จผ์ ์๊ฐํด๋ด ๋๋ค.
์ ๋ ์๋์ ๊ฐ์ด ์ ์ํ์ต๋๋ค.
- ์ฃผ์ด์ง n๋ณด๋ค ์ด๋ฆฐ ๊ดํธ๊ฐ ๋ ๋ง์ผ๋ฉด ์๋จ
- ์ง๊ธ๊น์ง ์ด๋ฆฐ ๊ดํธ๋ณด๋ค ๋ซํ ๊ดํธ๊ฐ ๋ ๋ง์ผ๋ฉด ์๋จ
- ๋ฌธ์์ด ์์ฑ ์์ ์๋ ์ด๋ฆฐ๊ดํธ์ ๊ฐฏ์์ ๋ซํ ๊ดํธ์ ๊ฐฏ์๊ฐ ๋ชจ๋ n์ด์ฌ์ผ ํจ
2. ํ์ด
์๋์ ๊ฐ์ด ์ด๋ฆฐ๊ดํธ ์, ๋ซ์์ผํ ๊ดํธ ์, ์ง๊ธ๊น์ง์ ๋ฌธ์์ด ์ด๋ ๊ฒ ์ธ ๊ฐ์ parameter๋ฅผ ๋ฐ๋ completeParenthesis ๋ฉ์๋๋ฅผ ๋ง๋ค์ด ํ์์ต๋๋ค.
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ret = []
# toOpen : ๋จ์ ์ด๋ฆฐ๊ดํธ ์
# toClose: ์ด๋ฆฐ๊ดํธ ์ - ๋ซํ ๊ดํธ ์ (๋ซ์์ผ ํ ๊ดํธ ์)
def completeParenthesis(toOpen, toClose, str):
if not toOpen and not toClose: return ret.append(str)
# ์ ๊ดํธ๋ฅผ ์ด์ด๋ ๋๊ณ
if toOpen is not 0: completeParenthesis(toOpen-1, toClose+1, str+'(')
# ๊ดํธ๋ฅผ ๋ซ์๋ ๋จ
if toClose is not 0: completeParenthesis(toOpen, toClose-1, str+')')
completeParenthesis(n, 0, '')
return ret
print(Solution().generateParenthesis(3))
print(Solution().generateParenthesis(1))
๋งค๋ฒ ์์ ํ ๊ดํธ์ธ์ง ํ์ธํ๋ค๊ฑฐ๋, ๋ถํ์ํ๊ฒ stack์ ๊ตฌ์ฑํ๋ ์ผ์ด ์์ผ๋ ์ํ์๋๊ฐ ์์ฃผ ๋น ๋ฅด๋ค์ ๐
์ฝ๊ธฐ์ฝ๊ณ , ์งง๊ณ , ์ฑ๋ฅ ์ข์ ์ฝ๋๋ฅผ ์ง์ ๋ฟ๋ฏํฉ๋๋ค
Time Complexity
์ ์ฒด ๊ฒฝ์ฐ์ ์๋ฅผ ๋ค ๋ง๋ค์ด์ผ ํ๋ ๋ฌธ์ ์ด๋ ์ต์ O(n!) ์ผ ๊ฒ ๊ฐ์ต๋๋ค.
Space Complexity
๋ณ๋ ๊ณต๊ฐ์ ์ฌ์ฉํ์ง ์์ต๋๋ค.
'์๊ณ ๋ฆฌ์ฆ > LEETCODE' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
Sort Colors | LeetCode 798 | Python3 ๐ (0) | 2022.03.06 |
---|---|
Permutations, Subsets | LeetCode | Python3 ๐ (0) | 2022.03.05 |
Letter Combinations of a Phone Number | LeetCode 793 | Python3 ๐ (0) | 2022.03.01 |
Longest Palindromic Substring | LeetCode 780 | Python3 ๐ (0) | 2022.02.28 |
Group Anagrams | LeetCode 778 | Python3 ๐ (0) | 2022.02.27 |