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

문제 링크

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

풀이 요약

• n개의 '('와 n개의 ')'를 이용한 조합 중 올바른 괄호쌍을 만들 수 있는 문자열의 갯수를 구한다

풀이 흐름

• 1차 풀이
  n개의 '('과 n개의 ')'를 이용한 만들 수 있는 모든 문자열을 만들고, 그 중에서 올바른 괄호쌍이 가능한 문자열을 골라서 갯수를 세려 함
  근데 동일한 문자가 n개 나와서 중복된 문자열이 너무 많이 나옴. 시간초과.
• 2차 풀이
  그럼 일단 처음부터 ')'이 나오는 경우는 항상 괄호쌍을 만족하지 않을테니까 첨부터 ')'가 나오는 경우는 만들지 않기로 함.
• 해설 참고
  2차 풀이를 다른말로 적으면, 닫히는 괄호의 개수가 열리는 괄호 개수보다 클 수 없다.

BFS와 DFS는

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

---

코드

해설코드

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> stack = new Stack<>();
    // Stack 대신 Queue를 사용해도 답을 얻을 수 있음
	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;
}