[프로그래머스, 12929] 올바른 괄호의 갯수 (java)

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

728x90

---

메모리: 93.6 MB, 시간: 26.49 ms

사용 알고리즘: 백트래킹, 완전 탐색

 

처음엔 괄호 모양에 따라 dp로 풀려고 했는데 예외가 너무 많은 것 같아서 포기

n의 최대가 14라 $2^{14}$ 밖에 걸리지 않으므로 그냥 완전 탐색으로 풀었다.

class Solution {
    
    static int n;
    static int answer;
    
    public int solution(int n) {
        
        this.n = n;
        
        answer = 0;
        backTracking(0, 0);
        return answer;
    }
    
    // open := 열린 괄호가 사용된 개수
    // close := 닫힌 괄호가 사용된 개수
    private static void backTracking(int open, int close) {
        
        if(open == n && close == n) {
            answer++;
            return;
        }
        
        // 올 수 있는 열린 괄호 개수가 남았다면
        if(open < n) {
            backTracking(open + 1, close);
        }
        
        // 올 수 있는 닫힌 괄호 개수가 남았다면
        if(open > close) {
            backTracking(open, close + 1);
        }
    }
}