[leetcode] 22. Generate Parentheses

오랫만에 코테 연습. 올 해 들어서 몇 문제 풀지 않았지만 그래도 10번째 문제 정도 되는 것 같다.
지난 번에 승지니어 강의 들으면서 외워둔 코드를 혼자서 다시 풀어봤다. 하루밖에 안지났는데도 처음엔기억이 안나더라..

이 문제의 핵심은 처음에 괄호를 어디서 부터 넣어줄지 생각하는 부분이었다. 아래 코드에서 보면 myparen + "(" 가 있는데 바로 이 부분을 생각하기까지 시간이 좀 걸렸다.

하지만 이 문제를 이진 트리로 접근하기 문제가 해결되었다. 처음에 두 가지 길이 있는데 이때 처음 길은 "(" 로 시작하는 것이고 그 다음 길은 ")"로 시작하는 것이다. 1 depth를 내려가서 똑 같은 작업을 계속 하는 거다. 여기까지 생각했다면 다 풀린 것이나 다름 없다.

그러니깐 트리로 보면

   "("      ")"
  /    \     /     \
"("  ")" "("  ")"
이런 식으로 내려가는 거다. 매 순간 할일은 "(" 또는 ")" 을 추가하기만 하면 되는 것이다. 그래서 각각 다른 괄호를 추가하며 진행하는 두 개의 함수가 재귀문 안에 등장한다.

나머지는 종료 조건인데,
닫는 괄호가 많아지면 종료되는 상황
그리고 하나의 괄호가 n 을 초과하는 상황
그리고 최종적으로 정답을 기록할 상황 (정상적으로 2*n개의 괄호가 모두 쌓인 상황) 을 정리하면 끝이난다.

class Solution:
    
    def generateParenthesis(self, n: int) -> List[str]:
        
        def progress(openparen, closeparen, myparen, result):
            # 닫힌 괄호가 더 많으면 백트래킹
            if openparen < closeparen:
                return None
            if openparen > n or closeparen > n:
                return None
            if len(myparen) == 2*n:
                return result.append(myparen)
            progress(openparen+1, closeparen, myparen+"(", result)
            progress(openparen, closeparen+1, myparen+")", result)
            
        myparen = ""
        result = []
        openparen = 0
        closeparen = 0
        progress(openparen, closeparen, myparen, result)
        return result