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 
별도 공간을 사용하지 않습니다.