[1스4코2파] # 179. LeetCode 22. Generate Parentheses

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (179차)
[4코1파] 2023.01.13~ (171일차)
[1스4코1파] 2023.04.12~ (82일차)
[1스4코2파] 2023.05.03 ~ (60일차)

Today :

2023.07.01 [179일차]
LeetCode Patterns
https://leetcode.com/problems/generate-parentheses/description/

22. Generate Parentheses

https://leetcode.com/problems/generate-parentheses/description/

문제 설명

n이 주어질 경우 n 개수에 해당하는 만큼 유효한 괄호를 만들어내는 것임

문제 풀이 방법

backtracking을 사용해서 풀이를 하는데
조건이 open parenthesis '(' 가 closed parenthesis ')' 보다 작으면 ')' 을 추가험

내 코드

from collections import deque
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        
        stack = []
        ans = []

        def backtrack(openN, closedN):
            if openN == closedN == n:
                ans.append(''.join(stack))
                return
            
            if openN < n:
                stack.append('(')
                backtrack(openN+1, closedN)
                stack.pop()
                
            if closedN < openN:
                stack.append(')')
                backtrack(openN, closedN+1)
                stack.pop()

        backtrack(0,0)
        return ans

증빙

여담

backtracking 나왔다 에효효