[리트코드 LeetCode] Generate Parentheses (Python)

Generate Parentheses

• https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/
• 분류: Top Interview Questions - Medium - Backtracking

Explore - LeetCode

문제

• 주어진 n개의 괄호 쌍에 대해, 가능한 모든 well-formed 괄호 쌍을 만드는 함수를 설계하라.
• type n: int / rtype: List[str]

예시

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

조건

• 1 <= n <= 8

풀이

백트래킹 - 임시 문자열에 ‘(’과 ‘)’를 추가하는 연산을 원하는 길이에 도달할 때까지 반복

1. ‘(’의 개수를 op, ‘)’의 개수를 cl로 세기 (left, right로 세어도 무방)
2. ‘(’를 붙여서 한 번, ‘)’를 붙여서 또 한 번 백트래킹 실행
3. ‘(’의 개수(op)가 n과 같아지면 남은 개수만큼(n-cl) 뒤에 ‘)’ 붙여서 종료
4. ‘(’의 개수보다 ‘)’의 개수가 더 많으면 안되므로 이 경우 (op < cl) 바로 종료 (well-formed여야 하므로)

class Solution(object):
    def generateParenthesis(self, n):
        ans = []
        temp = ''
        def backtracking(op, cl, tmp):
            if op < cl:
                return
            if op == n:
                tmp += ')' * (n - cl)
                ans.append(tmp)
                return
            tmp += '('
            backtracking(op+1, cl, tmp)
            tmp = tmp[:-1]
            tmp += ')'
            backtracking(op, cl+1, tmp)
            tmp = tmp[:-1]
        backtracking(0, 0, temp)
        return ans

Runtime: 16 ms (beats 88.62%) / Memory Usage: 13.6 MB (beats 89.4%)

 

tmp 부분을 간추린 코드

호출 시에 인자로 tmp + ‘(’을 넣어주는 것이므로 tmp 자체는 변하지 않기 때문에 따로 맨 뒤의 문자를 빼줄 필요 없이 다음 백트래킹을 호출할 수 있음

class Solution(object):
    def generateParenthesis(self, n):
        ans = []
        def backtracking(op, cl, tmp):
            if op < cl:
                return
            if op == n:
                tmp += ')' * (n - cl)
                ans.append(tmp)
                return
            backtracking(op+1, cl, tmp + '(')
            backtracking(op, cl+1, tmp + ')')
        backtracking(0, 0, '')
        return ans

Runtime: 14 ms (beats 93.92%) / Memory Usage: 13.8 MB (beats 18.81%)

 

같은 아이디어지만 (, )를 붙여 순차적으로 호출한 후 op < cl로 거르는 방법 말고

op < n인 경우에 (를 붙이고, op > cl인 경우에 )를 붙이는 방법을 사용할 수도 있음

• 코드 출처

def generateParenthesis(self, n):
    def dfs(left, right, s):
        if len(s) == n * 2:
            res.append(s)
            return 

        if left < n:
            dfs(left + 1, right, s + '(')

        if right < left:
            dfs(left, right + 1, s + ')')

    res = []
    dfs(0, 0, '')
    return res

Runtime: 25 ms (beats 35.39%) / Memory Usage: 13.8 MB (beats 18.81%)

 

문제를 풀 때 겪은 문법적 오류

1) str형 변수 temp를 함수 외부에서 선언한 후 함수 내부에서 바로 로컬 변수로 접근하려고 할 때 unboundlocalerror: local variable 'temp' referenced before assignment

이 경우 backtracking 함수 내부에서 global temp로 전역변수 선언을 해주면 되지만 전역 변수 사용은 자제하는 것이 좋으므로 인자로 tmp를 넘겨주는 방식으로 변경했다.

 

2) 백트래킹 이후 직전에 추가한 괄호를 문자열에서 삭제할 때

문자열에는 +, * 연산은 있지만 빼기(-) 연산은 없다. 따라서 문자열 슬라이싱으로 맨 뒤의 문자를 삭제했다. 이때 tmp[:] = tmp[:-1] 을 하면 TypeError: 'str' object does not support item assignment 에러가 난다. str형은 immutable한 자료형이므로 같은 주소에 새로운 값을 할당할 수 없고, 새로운 값을 할당한 새로운 주소를 참조하는 식으로 변수가 가진 값을 변경할 수 있기 때문이다.

 

문자열과 배열의 참조 범위와 방식이 다르다는 점을 항상 유의하자.