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

문제 설명

n개의 괄호 쌍으로 만들 수 있는 올바른 괄호의 갯수를 반환하는 함수를 완성하라.

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미한다.

문제 이해

• 모든 케이스를 다 순회하면서 조건에 맞는 경우만 카운트하면 된다.
• 괄호가 열렸다 닫히면서 여러 케이스가 생기고, 각 케이스에서 열리고 닫히는 순서를 달리하면서 또 다른 케이스가 파생되므로 선형으로 증가하지 않는다.
• 비선형적으로 탐색하는 것 중 dfs(깊이우선탐색)을 사용한다.

---

그림으로 이해

• (열리는 괄호, 닫히는 괄호)를 2차원 좌표로 표현하니 규칙을 찾는 게 수월했다.
• 각각 괄호 갯수가 n과 같으면 올바른 괄호로 보고 갯수 count 값을 +1 해주면 된다. 그 전에, 올바르지 않은 괄호는 count되지 않도록 검사가 필요하다.
  • 시작은 열린 괄호부터
  • 열린 괄호가 n보다 클 수 없다.
  • 닫힌 괄호 갯수가 열린 괄호 갯수보다 클 수 없다.

슈도코드

class Solution {
    public int solution(int n) {
        int answer = 0;

        P(open, close)를 저장하는 stack을 만든다.
        stack에 시작노드 P(1,0)을 추가한다.(열린괄호로 먼저 시작해야한다.)
        while(스택이 빌 때까지 반복한다.){
            가장 위에 있는 노드 P를 꺼낸다.
            
            if(open이 n보다 크면){
                아래 코드 실행하지 않는다.
            }
            
            if(close보다 open이 크면 ){
                아래 코드 실행하지 않는다.
            }
            
            if(open과 close가 모두 사용되었으면){
                answer를 1 증가시킨다.
            }
            
            stack에 열린괄호(open +1)를 추가한다.
            stack에 닫힌괄호(close + 1)를 추가한다.
        }
        return while문 종료 후 answer를 반환한다.
    }
}

구현 코드

import java.util.*;

class Solution {
    
    class P{
        int open; 
        int close;
        P(int open, int close){
            this.open = open;
            this.close = close;
        }
    }
    
    public int solution(int n) {
        int answer = 0;
        
        Stack<P> stack = new Stack<>();
        stack.push(new P(1,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;
    }
}