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

• 문제 링크 : 올바른 괄호의 갯수

코딩테스트 연습 - 올바른 괄호의 갯수

 

정답(Solution)

import java.util.*;

class Solution {

    private 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> st = new Stack<>();
        st.push(new P(0,0));

        while(!st.isEmpty()){
            P p = st.pop();

            if(p.open > n) continue;
            if(p.open < p.close) continue;
            if(p.open + p.close == 2 * n) {
                answer++;
                continue;
            }

            st.push(new P(p.open + 1, p.close));
            st.push(new P(p.open, p.close + 1));
        }

        return answer;
    }
}

 

분석

• dfs로 풀이하였다.
• dfs는 기본적으로 Stack을 사용한다.