[LeetCode] 22. Generate Parentheses - 완전탐색(BuretForce) + 아이디어(Idea) JAVA

https://leetcode.com/problems/generate-parentheses/description/

코드설명

완전탐색(BuretForce) 를 활용합니다.

 

처음부터 Well-Formed만 만들어내기는 어렵다고 판단하여, 모든 경우를 만들고, 그 중에 Well-Formed만 필터링해나갔습니다.

 

하지만, 처음부터 Well-Formed를 만들어내는 훨씬 효율적인 방식이 존재합니다.

코드

모든 경우를 다 만들고 Well-Formed만 걸러내는 코드입니다.

import java.util.*;
class Solution {
    //make whole and filtering well-formed Parenthese
    // Time COmplexity : : O(2^16) = 1024 * 32
    List<String> answer = new ArrayList<String>();
    public List<String> generateParenthesis(int n) {
        DFS(n, n, new Stack<Character>());
        return answer;
    }

    void DFS(int o, int c, Stack<Character> st){
        if(o == 0 && c == 0){
            //cannot init by deep copy with parameter st. check it. 
            // Stack<Character> storeSt = new Stack<>(st);
            Stack<Character> newStack = new Stack<>();
            for(Character v : st){
                newStack.push(v);
            }
            if(isWellFormed(newStack)){
                StringBuilder sb = new StringBuilder();
                for(Character v : st){
                    sb.append(v);
                }
                answer.add(sb.toString());
            }
            return ;
        }

        if(o > 0){
            st.push('(');
            DFS(o - 1, c, st);
            st.pop();
        }
        if(c > 0){
            st.push(')');
            DFS(o, c - 1, st);
            st.pop();
        }
        return ;
    }
    boolean isWellFormed(Stack<Character> st){
        int cCnt = 0;
        while(!st.isEmpty()){
            Character  ch = st.pop();
            if(ch == ')'){
                cCnt += 1;
            }
            else if(ch == '('){
                if(cCnt == 0){
                    return false;
                }
                cCnt -= 1;
            }
        }

        return true;
    }

}

 

더 효율적인 방식입니다. 처음부터 Well-Formed만 만들어냅니다.

이 풀이의 경우 '('가 항상 ')'보다 먼저 앞에 있어야 한다는 특징을 이용한 코드입니다.

즉, ')'의 경우 항상 '('가 ')'의 개수보다 많아야만 괄호를 닫을 수 있습니다.

import java.util.*;
class Solution {
    List<String> answer = new ArrayList<String>();
    int N;
    public List<String> generateParenthesis(int n) {
        N = n;
        DFS(0, 0, new String(""));
        return answer;
    }

    void DFS(int o, int c, String str){
        if(o == c && o + c == N * 2){
            answer.add(str);
            return ;
        }

        if(o < N){
            DFS(o + 1 , c, str + "(");
        }

        if(o > c){
            DFS(o, c + 1, str + ")");
        }
    }

}