๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์•Œ๊ณ ๋ฆฌ์ฆ˜/LEETCODE

Generate Parentheses | LeetCode 780 | Python3 ๐Ÿ

๋ฐ˜์‘ํ˜•

 

๐Ÿ“„ ๋ชฉ์ฐจ

     

     

    ๐Ÿค” ๋ฌธ์ œ : 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 
    ๋ณ„๋„ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. 

     

    ๋ฐ˜์‘ํ˜•