[프로그래머스 Level 4] 올바른 괄호의 갯수 [자바]

 

 

---

※. 열린 괄호, 닫힌 괄호 를 구별하고 괄호쌍의 조건에 맞게 재귀

(n * 2 -> 괄호쌍의 갯수 * (열린괄호 + 닫힌괄호) = 2

 

class Solution {
    public int solution(int n) {
        int answer = bracket(0,0,n*2);
        return answer;
    }
    static int bracket(int open, int close, int n) {
        if(open + close == n) {
            return 1;
        }
        int answer = 0;
        if(open < n/2) {
            answer += bracket(open+1, close, n);
        }
        if(open > close) {
            answer += bracket(open, close+1, n);
        }
        return answer;
    }
}

스택

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;
        Stack<P> stk = new Stack<>();
        stk.push(new P(0,0));
        
        while(!stk.isEmpty()) {
            P p = stk.pop();
            
            if(p.open > n) continue;
            if(p.open < p.close) continue;
            if(p.open + p.close == 2*n) {
                answer++;
                continue;
            }
            
            stk.push(new P(p.open+1, p.close));
            stk.push(new P(p.open, p.close+1));
        }
        
        return answer;
    }
}