[LeetCode][Python] 22. Generate Parentheses

- 문제 링크: https://leetcode.com/problems/generate-parentheses/

- 난이도: Medium

 

n개의 well-formed 괄호들을 만드는 문제다.

n 범위가 [1,8]이라서 최대 순열은 256개밖에 안된다. 모든 순열을 만들고 괄호 유효성 검사하는것도 방법이지만 좀 더 나은 방법을 생각해보자.

 

열린 괄호 left개, 닫힌 괄호 right개를 이용했다고 했을 때, left < n 이라면 열린 괄호를 추가할 수 있다. right < left라면 (지금까지 열린 괄호가 더 많다면) 닫힌 괄호를 추가할 수 있다.

이렇게 괄호 추가하는게 가능한 경우만 추가하면 나중에 따로 검사하지 않아도 된다

 

스택과 큐를 이용한 풀이를 각각 써보면 아래와 같다

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ret = []

        def dfs(left: int, right: int, s: str) -> None:
            if len(s) == n*2:
                ret.append(s)
                return
            
            if left < n:
                dfs(left + 1, right, s + '(')
            
            if right < left:
                dfs(left, right + 1, s + ')')

        dfs(0, 0, '')

        return ret

 

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ret = []

        left = right = 0
        q = [(left, right, '')]
        while q:
            left, right, s = q.pop()
            if len(s) == n*2:
                ret.append(s)
                continue

            if left < n:
                q.append((left + 1, right, s + '('))

            if right < left:
                q.append((left, right + 1, s + ')'))

        return ret