LeetCode: generate-parentheses

오늘은 dynamic programming문제를 풀고 리뷰하려고 한다. 

 

리뷰 시작~!

 

 

문제는 매우 간단하게 설명이 되어있다. 

 

문제를 푸는 방법은 여러가지가 있을 것 같지만 나는 백트레킹과 dfs를 조합하여 풀었다. 

 

local에서 푼 뒤에 leetcode를 적으려고 했는데, leetcode는 class형식으로 코드를 짜야해서 

다시 코드를 변경하느라 고생했다.. (좀 더 문제를 잘 읽어야겠다. )

 

문제를 푼 방식은 다음과 같다. 

 

재귀형태의 dfs함수를 만든다. 

 

여기에 현재까지 만들어진 괄호 문자열을 전달하는 인자, 문자열의 최대 길이, '(' 남은 수, ')' 남은 수 등을

파라미터로 전달했다. 

 

• curr_pt: 현재까지 만들어진 괄호 문자열을 전달하는 인자
• limit_len: 문자열의 최대 길이
• left_pt_num: '(' 남은 수
•  right_pt_num: ')' 남은 수

 

백트레킹을 하는 조건은 당연히 len(curr_pt) == limit_len이다.

-> 이때 결과를 res 리스트에 append해줬다. 

 

끝내는 조건이 아니라면 괄호를 추가시켜줘야 한다. 

 

괄호 추가 방법:

 

for pt in ['(', ')'] 의 반복문안에

 

만약 pt == '(' and left_pt_num( 왼쪽 괄호남은 개수) != 0 이라면

-> dfs(curr_pt + pt, limit_len, left_pt_num -1, right_pt_num) 으로 재귀 호출을 해준다. 

 

만약 pt == ')' and right_pt_num( 왼쪽 괄호남은 개수) != 0 그리고 left_pt_num < right_pt_num이라면

-> dfs(curr_pt + pt, limit_len, left_pt_num, right_pt_num) 으로 재귀 호출을 해준다. 

 

변수자체에 변화를 주는 것이 아니라 파라미터에 대해서만 변화를 주어야 백트레킹을 하고 돌아왔을 때

변수도 변화가 없다. 

 

left_pt_num < right_pt_num

-> ( 가 )보다 먼저 와야함

 

 

이게 문제에서 제시하는 올바른 괄호가 될 조건이다. 

( 가 )보다 먼저 와야하고 (와 )가 동일한 개수여야 하기 때문임. 

 

---

 구현코드

로컬용

from collections import deque

res = []

def dfs(curr_pt, limit_len, right_pt_num, left_pt_num):
    
    if len(curr_pt) == limit_len:
        res.append(curr_pt)

    for pt in ['(', ')']:
        if pt == '(' and left_pt_num !=0:
            dfs(curr_pt + pt, limit_len, right_pt_num, left_pt_num-1) # 재귀 호출

        elif pt == ')' and right_pt_num != 0 and left_pt_num < right_pt_num:
            dfs(curr_pt + pt, limit_len, right_pt_num-1, left_pt_num) # 재귀 호출

n = 3
dfs('', n*2, n, n)
print(res)

 

 

제출용

class Solution(object):
    def __init__(self):
        self.res = []

    def dfs(self, curr_pt, limit_len, right_pt_num, left_pt_num):
    
        if len(curr_pt) == limit_len:
            self.res.append(curr_pt)

        for pt in ['(', ')']:
            if pt == '(' and left_pt_num !=0:
                self.dfs(curr_pt + pt, limit_len, right_pt_num, left_pt_num-1)

            elif pt == ')' and right_pt_num != 0 and left_pt_num < right_pt_num:
                self.dfs(curr_pt + pt, limit_len, right_pt_num-1, left_pt_num)

    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        self.dfs('', n*2, n, n)
        return self.res

 

이상 포스팅을 마치겠다~!