[리트코드] 22. Generate Parentheses

안녕하세요. 개발조각입니다.😊

이번 문제도 어떻게 풀어야 될지 몰라서 검색해서 풀어보았습니다.

이번 문제 계기로 재귀 함수를 어떻게 써야 되는지 파악하게 된 것 같아서 기분이 좋아요~

---

https://leetcode.com/problems/generate-parentheses/

Generate Parentheses - LeetCode

 

아래의 블로그를 참고해서 풀어보았습니다.

https://underdog11.tistory.com/entry/JavaScript-22-Generate-Parentheses

[JavaScript] 22. Generate Parentheses 풀이과정 쉬운 설명 - backtrack, recursion 활용

 

이게 무슨 법칙으로 풀었는지는 참고한 블로그에선 backtracking이라고 하는데

 backtrack은 recursion을 이용해서 모든 경우의 수를 접근하는 알고리즘입니다. 
우리가 미로찾기를 할 때 탈출구를 찾는 방법이라 생각하시면 됩니다.

라고 나와있습니다.

 

 

 

제가 쓴 느낌으로는 이 방식으로 설명하자면

경우의 수 구하기(재귀함수)에서 원하는 해결만 구하기 위해 답이 아닌 건 미리 차단하기(if문)

같은 느낌이였습니다.

 

저는 이 문제를 어떻게 파악하고 풀었는지 위주로 설명하겠습니다.

---

 

먼저 코드를 살펴보기 전에

짝이 맞는 () 괄호에 대해 설명해 보겠습니다.

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

이러한 조건이 있으면 ()괄호 3개를 다 사용해서 짝이 맞는 괄호의 경우의 수를 다 구해야 됩니다.

자세히 보시면 규칙이 보일 겁니다.

 

 

 

짝이 맞는 괄호 경우의 수 구하기의 필수조건

1. 첫 괄호는 무조건 '('이어야 한다.
2. 괄호의 총개수는 n *2이다.
3. 괄호는 '(' n개, ')' n개이며, '('가 먼저 n 개여야 된다.
4. 앞에서부터 괄호를 세보면 '('가 n개가 되기 전까지 무조건 '(' > ')'이다.

 

 

 

위에 있는 조건을 토대로 그려보면 아래와 같이 됩니다.

여기를 보시면

• '('가 3개 → ')'
• '('의 개수가 3이 아니면 '('의 개수 > ')'의 개수 → '('

이렇게 됩니다.

 

 

즉 저희가 코드로 써야 되는 건

• 재귀 함수에서 탈출 조건 만들기
  • 짝이 맞는 문자열의 길이가 n*2인 괄호 문자열을 다 만들어주면 빠져나오기
• 갈림길 조건을 적어주어 짝이 맞는 괄호를 만들기
  • '('일 때 조건
  • ')'일 때 조건

이렇게 써주면 됩니다.

---

해결방안

var generateParenthesis = function(n) {
    const result = [];
    makeBranckes('(', 1, 0)
    
    return result;
    
    function makeBranckes(str, left, right){
        if(str.length === 2*n){
            result.push(str);
            return;
        }
        
        if(left < n){
            str+= '(';
            makeBranckes(str, left+1, right);
            str = str.slice(0, -1)
        }
        
        if(left > right){
            str+= ')';
            makeBranckes(str, left, right+1);
        }
    }
};

 

makeBranckes('(', 1, 0)

재귀 함수에 넣어줄 조건으로 str, left, right를 넣어주었습니다.

• str : 괄호 조합 문자열
• left : '('의 개수
• right : ')'의 개수

짝이 맞는 괄호 경우의 수 구하기의 필수조건에서

1. 첫 괄호는 무조건 '('이여야 한다.

라는 조건이 있었습니다.

 

그래서 초기값을 '('로 설정 해고 left를 1으로 해주었습니다.

 

 

 

if(str.length === 2*n){
    result.push(str);
    return;
}

이제 재귀 함수를 써주는데

재귀함수를 만들 때는 상단에 탈출 조건을 만들어줘야 됩니다.

 

짝이 맞는 괄호 경우의 수 구하기의 필수조건에서

2. 괄호의 총개수는n *2이다.

라는 조건이 있었습니다.

 

그래서 탈출 조건에 str길이가 n*2이면 result에 담아주고 return을 해주었습니다.

 

 

 

if(left < n){
    str+= '(';
    makeBranckes(str, left+1, right);
    str = str.slice(0, -1)
}

if(left > right){
    str+= ')';
    makeBranckes(str, left, right+1);
}

이게 갈림길 조건에 대해 설명하자면

갈림길은 '('로 갈지, ')'로 갈지에 대해 정해주면 됩니다.

 

위에서

• '('가 3개 → ')'
• '('의 개수가 3이 아니면 '('의 개수 > ')'의 개수 → '('

이 말을 분석을 하자면

 

결국

'('가 n보다 작으면 되는 거고 이경우에는 str에 '('를 추가해주면 되는거고

'('의 개수 > ')'이면 ')'를 추가하면 되는 겁니다.

 

 

그럼 갈림길의 조건을 썼는데

밑 에보시면

makeBranckes(str, left+1, right);
str = str.slice(0, -1)

이렇게 쓴 부분이 이해가 잘 안 되실 거예요.

(제가 그랬거든요.)

 

저는 아래 방식으로 이해했습니다.

makeBranckes(str, left+1, right); // 다음단계로 가기 위한 방법
str = str.slice(0, -1) // 다른 갈림길을 가기 위한 방법

 

 

 

그래도 이해가 안 가시면 아래 있는 이미지를 보시고 이해하셨으면 좋겠습니다.

(저는 머리가 딸려서 손으로 쓰면서 이해를 했습니다.😂)

일부만 쓰긴 했지만

이런 식으로 복사본을 만들어서 진행이 되고 str.length === n*2가 되면 종료하게 됩니다.

---