[Algorithm] LeetCode 22. Generate Parentheses in Python

💡 LeetCode 22:

모든 n 개의 괄호 조합 찾기

🌱 코드 in Python

알고리즘: DFS

class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        ans = []
        
        def dfs(left, right, s):
            if len(s) == n * 2:
                ans.append(s)
                return
            if left < n:
                dfs(left + 1, right, s + "(")
            if left > right:
                dfs(left, right + 1, s + ")")
        
        dfs(0, 0, "")
        return ans

처음 문제를 읽고 어떤 식으로 dfs를 풀어나가야 할지 감이 안 잡혀서
아예 풀어서 쭉 한 번 보기로 했다.

3개를 예로들면 아래와 같이 구성할 수 있다고 생각했다.

( -> ( -> ( -> ) -> ) -> )
       -> ) -> ( -> ) -> )
            -> ) -> ( -> )
 -> ) -> ( -> ( -> ) -> )
           -> ) -> ( -> )

백트래킹의 특성상 뒤에서부터 앞으로 올라와서 경로를 수정해 나가는 식으로 구성하였다.

여기서 알아낼 수 있었던 것은 두가지였다.

1) 당연히 여는 괄호가 닫는 괄호에 우선한다
2) 닫는 괄호는 여는 괄호보다 작은 만큼 사용됐을 때만 쓸 수 있다

그리고

( -> ( -> ( -> ) -> ) -> )
       -> ) -> ( -> ) -> )

이 부분에서 경로가 수정되는 것을 보고
모든 자리에 대해 "(", ")" 이 괄호 쌍을 한 번씩 검사하고
넣을 수 있을때만 넣어서 재귀문을 종료시켜야 한다는 생각이 들었다.

그래서 해당 자리에 첫번째 dfs 호출일 경우 여는 괄호를 다 썼는가?를 검사 후,
쓰지 않았다면 여는 괄호를 쓰도록 했다.

그리고 두번째 dfs 호출일 경우 닫는 괄호가 여는 괄호보다 적은가?를 검사 후,
적다면 닫는 괄호를 쓰도록 했다.

이렇게하면 처음 ((())) 이 괄호 조합을 볼때
첫 세자리까지는 첫번째 if문까지 내려온 상태이고,
))) 이 세개는 두번째 if문까지 돌아 종료된 상황이다.
따라서 ((')' <- 요 자리부터 다시 검사를 시작할 수 있게 되는 것이다.

나 이제 좀 DFS 알 것 같아~~!

근데 처음에는 한 자리당 모두 두 번 검사해야 한다에 너무 빠져가지고

for i in range(2):
  if i == 0:
    if left < n:
      dfs(left + 1, right, s + "(")
  else:
    if left > right:
       dfs(left, right + 1, s + ")")

이딴 해괴망측한 코드를 작성하고 말았다.. 🤦🏻‍♀️
반성 또 반성..!!!

그리고 또 하나의 실수가 있었는데

s += ")"
dfs(left, right + 1, s)

이렇게 s를 직접 건드리다보니 문제가 발생했었다.
첨엔 대체 뭐가 문젠지 몰라서 엉엉 울고싶었음 또륵.

저렇게 작성하면 세번째 자리를 다시 검사하려고 할 때
내가 원한 것은 "((" + ")" 였는데 앞선 if 문에서 이미 문자열이 "(((" 수정된 상태기 때문에
"(((" + ")" 요 따위의 결과가 나타난다.

객체 원본을 수정하는 경우와 원본을 수정하면 안되는 경우를 꼭 분리해서 생각하도록 하자!!

---

🧠 기억하자

1. DFS에서는 원본이 "훼손"되는 지점을 잘 파악해야 한다.

LeetCode 22 바로가기