Lv.4 [깊이우선탐색] - 올바른 괄호의 갯수 (풀이 미완성)

---

[ 문제 링크 ]

프로그래머스 Lv4. 올바른 괄호의 갯수

 

[ 문제 설명 이미지 ]

 

올바른 괄호의 갯수

A 입력값으로 괄호쌍의 갯수가 주어지고 이 괄호의 조합중에 올바르게 닫힌 괄호의 갯수가 몇개인지 구하는 문제
모든 케이스를 다 순회하면서 조건에 맞는 경우만 카운트한다.
괄호가 열렸다가, 닫혔다가 하면서 점점 증가하며 여러 케이스가 생기고
각 케이스에서 열리고 닫히는 순서를 달리하면서 또 다른 케이스들이 파생되기 때문에
선형적으로 증가하지 않게되므로 비 선형구조 탐색에서는 너비,깊이 우선 탐색이 있다.


N = 2라고 가정
주어진 괄호를 하나씩 차근차근 쌓아나가것으로 문제를 접근한다.
열리는괄호 닫히는괄호 각각 N개씩있다.
N이 2일때 열리는것 혹은 닫히는것 각각의 기준을 놓고 시작할 수 있다.
그러나 열리지 않고 닫히는것은 올바른 괄호가 아니므로 이 경우는 제외된다.
) X
열린 후에는 열릴수도있고 닫힐수도 있다.

[열린 후 열린케이스]
(( -> )) 열린 케이스에서는 두개의 괄호를 모두 사용해버렸기 때문에 닫히는 케이스밖에 없다.
[열린 후 닫힌케이스]
() -> () 닫힌 케이스에서는 다시 열린케이스와 닫힌케이스가 있을 수 있다.
() -> )( X 닫힌 후 새롭게 열리지않고 다시 닫힐 수 없으므로 사용불가능

[도출된 규칙]
1. 열리는 괄호를 먼저 배치한다.
2. 그 이후에 닫히는 괄호를 배치한다.
3. 괄호는 N개 이상 사용할 수 없다.
4. 열리기 전에는 닫히는 괄호를 사용할 수 없다.

3번 규칙에 의해서 괄호의 갯수를 N과 비교해야 한다.
괄호를 몇개 사용했는지에 대해 알고 있어야 한다.

4번 규칙을 갯수에 대한 조건으로 바꿔서 표현하면
닫히는 괄호의 갯수는 열리는 괄호의 갯수보다 클 수 없다.

Stack

깊이 우선 탐색은 Stack을 사용한다.

Stack을 사용해서 열린 경우와 닫힌 경우에 대한 카운트를 각각 증가시킨다.

Loop 를 돌 때 마다 쌍의 갯수보다 큰지, 올바른 괄호 조건인지, 그리고 종료 조건에 부합하는지를 먼저 체크하고

꺼낸 경우를 기준으로 열린 괄호와 닫힌 괄호의 경우에 대한 카운트를 증가시킴으로써 깊이를 늘려나간다.

다시 Loop를 돌아 위 과정을 반복하여 깊이를 계속 탐색해 나간다.

---

[풀이] 

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> stack = new Stack();
        stack.push(new P(0,0)); //시작값 초기화
        while(!stack.isEmpty()) {
            P p = stack.pop(); //일단 꺼내고 시작. 두번째 루프라면 열린괄호가 꺼내진다.
            if(p.open > n) continue; // 닫히는것부터 시작했으므로, 닫히는게 n보다 커질수 없다.
            if(p.open < p.close) continue; //올바른 괄호 조건 (닫히는 괄호 갯수가 열리는 괄호 갯수보다 크면 안된다. - 크면 열린괄호보다 먼저 닫힌경우)
            if(p.open + p.close == 2*n) { // 종료 조건 (열리는것과 닫히는것을 합하여 쌍의 값이 n * 2가 됨)
                answer ++;
                continue;
            }

            /* 2쌍의 경우를 추가 */
            stack.push(new P(p.open+1, p.close)); //열린괄호 `경우`추가
            stack.push(new P(p.open, p.close + 1)); //닫힌괄호 `경우`추가
        }

        return answer;
    }
}

 

 

그래프로도 표현할수 있다.

---