🎯2주차B "올바른 괄호의 개수"

🎃문제설명

🍬올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

🔒제한사항

괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

💾입출력 예

n	result
2	2
3	5

입출력 예 #1

2개의 괄호쌍으로 [ "(())", "()()" ]의 2가지를 만들 수 있습니다.

입출력 예 #2

3개의 괄호쌍으로 [ "((()))", "(()())", "(())()", "()(())", "()()()" ]의 5가지를 만들 수 있습니다.

---

🌟문제 이해 및 풀이계획

✏️사실, 처음 문제를 봤을 때는 어떤식으로 풀어야 할 지 감이 안왔다. 이미 있는 문자열을 검수하는 것이 아닌 개수에 맞는 모든 쌍의 경우를 찾아야 했으므로 완탐을 해야하나? 라고 생각도 했다.
✏️완탐보다는 더 효율적인 방법이 있을 것 같아서 검색을 통해 "카탈란 수(catalan number)" 수열을 이용하여 간단하게 풀이 할 수 있음을 알게 되었다.
✏️"카탈란 수(catalan number)" 점화식

c[0] == 1, n >= 1
c[n] = c[0]*c[n-1] + c[1]*c[n-2] + ... + c[n-2]*c[1] + c[n-1]*c[0]

✏️참고 링크 : https://suhak.tistory.com/77

✍🏻내 코드

class Solution {
    public int solution(int n) {
        int[] catalan = new int[n+1];

        // 카탈란 수 점화식 이용
        catalan[0] = 1;
        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                catalan[i] += catalan[j]*catalan[i-j-1];
            }
        }

        return catalan[n];
    }
}

🍭강의내용

✔️모든 케이스를 다 순회하면서 조건에 맞는 경우만 세준다.
✔️선형 구조의 탐색법 중 (BFS/DFS) DFS를 이용할 수 있다.
✔️풀이방법

1. 열리는 괄호를 배치한다.
2. 그 이후에 닫히는 괄호를 배치한다.
3. 괄호는 N개 이상 사용할 수 없다.
4. 열리기 전에 닫히는 괄호를 사용할 수 없다.
   => 닫히는 괄호의 개수는 열리는 괄호의 개수보다 클 수 없다.

✍🏻강의 코드

import java.util.*;

class Solution {
    
    class P {
        int open, close;
        P(int open, int close) { // 생성자
            this.open = open;
            this.close = close;
        }
    }
    public int solution(int n) {
        int answer = 0;
        
        // Queue<P> queue = new LinkedList<>();
        Stack<P> stack = new Stack<>();
        stack.push(new P(0,0)); // 시작값
        while(!stack.isEmpty()) {
            P p = stack.pop();
            
            if(p.open > n) continue;
            if(p.open < p.close) continue;
            if(p.open + p.close == 2*n) {
                answer++;
                continue;
            }
            
            stack.push(new P(p.open+1, p.close)); // 열리는 괄호 
            stack.push(new P(p.open, p.close+1)); // 닫히는 괄호
        }
        return answer;
    }
}

✔️Stack대신 Queue를 이용해도 결과는 같다.

💡강의 Tip
너비우선탐색(BFS)/깊이우선탐색(DFS)

• 비선형 데이터를 순회하는 방법
• 두 방법의 차이는 순서가 다르다는 점이다.
• 순서를 무시하면 두 방법의 결과는 동일하다.

💡처음에는 머리로 잘 그려지지 않았지만, 강의를 보고 예시를 적어보면서 처음 순서를 '('로 시작하면서 '('와 ')'를 모두 체크하면서 되는 경우를 세어주고 있는 방법임을 알 수 있었다.