[LeetCode 해석 및 풀이] 22. Generate Parentheses

LeetCode 문제 해석 및 풀이 방법

 

문제22. Generate Parentheses(괄호 생성)

바로가기

 

문제 설명

영문

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

한글

n쌍의 괄호가 주어지면, 모든 조합의 잘 만들어진 괄호형태를 생성하는 함수를 작성하시오.

 

제한조건

• 1 <= n <= 8

 

입출력 예

입력	출력
n = 3	["((()))","(()())","(())()","()(())","()()()"]
n = 1	["()"]

 

 

해답 및 해설

파이썬 (Python)

이전 유효한 괄호 문제에서 괄호는 stack으로 관리하면 쉽다는걸 알았을 것이다.

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def get_next(state:str, count:int, stack:int) -> List[str]:
            if count == 0 == stack: return [state]

            result = []
            if count > 0:
                result += get_next(state+'(', count-1, stack+1)
            if stack > 0:
                result += get_next(state+')', count, stack-1)

            return result
        
        return get_next('', n, 0)

그래서 이번에도 stack으로 괄호가 유효한지 관리해준다. 그리고 재귀를 이용해 문제를 풀어준다.

 

재귀함수 get_next에 state에는 현재 놓여진 괄호 상태, count에는 앞으로 놓을 수 있는 괄호의 갯수, stack에는 현재 열려있는 괄호의 갯수를 입력받는다. count나 stack이 0보다 크면, 열린 또는 닫힌 괄호를 넣은 다음 상태를 재귀함수로 불러온다. count와 stack이 둘 다 0이면 해당 상태가 최종 상태이므로, state를 반환한다.