[C++] LeetCode : Generate Parentheses

Question

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

n개의 쌍으로 이루어진 괄호가 주어진다면, 해당 괄호 쌍으로 만들어낼 수 있는 모든 조합을 만들어내는 함수를 작성하라. 단 만들어낸 조합은 well-formed 해야 한다. 

제약사항

• n은 1이상 8 이하이다. 

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

   보통 괄호 관련된 문제를 풀 때는 stack을 많이 사용한다. BCR 먼저 생각해보려 했지만, 쉽진 않을 것 같아 바로 풀이를 생각해본다. 

고려사항

---

Solution1 (Bruth Force)

가장 쉽게 생각할 수 있는 풀이는, 
1차로 괄호 3 쌍으로 만들 수 있는 모든 경우의 수를 생성한 뒤, 그중 well-formed 된 괄호 쌍만 추려낸다. 

간단하게 재귀를 사용하여 가능한 모든 경우의 수를 생성해내고, 추가로 well-formed 조건에 맞게 일부 조건에 맞지 않는 경우 잘라낸다. 

void make_parentheses(vector<string> &ans, string s, int n, int left, int right){
	if(letf > n || right > n) return;
	if(s.size() == n * 2){
		ans.push_back(s)
		return;
	}

	make_parentheses(ans, s + '(', n, left+1, right);
	make_parentheses(ans, s + ')', n, left, right+1);
}

well formed 되어있는지 확인하는 코드는 아래와 같이 stack을 이용해 구현할 수 있다. 
'('가 올 때는 stack에 쌓고 ')'가 올 때는 pop을 하며 이상한 동작을 하지 않는다면 well formed 되었다고 볼 수 있다.

bool check_well_formed(string s){
	stack<char> my_stack;
	for(auto c : s){
		if(c == '('){
			my_stack.push(c);
		}else{
			if(my_stack.empty()) return false;
			my_stack.pop();
		}
	}	
	return true;
}

이를 조합하여 make_parenthese 에서 바로 검사할 수 있도록 한다. 

class Solution {
public:
    bool check_well_formed(string s){
        stack<char> my_stack;
        for(auto c : s){
            if(c == '('){
                my_stack.push(c);
            }else{
                if(my_stack.empty()) return false;
                my_stack.pop();
            }
        }
	    return true;
    }
    
    void make_parentheses(vector<string> &ans, string s, int n, int left, int right){
        if(left > n || right > n) return;
        if(s.size() == n * 2 && check_well_formed(s)){
            ans.push_back(s);
            return;
        }

        make_parentheses(ans, s + '(', n, left+1, right);
        make_parentheses(ans, s + ')', n, left, right+1);
    }
    
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        make_parentheses(ans, "", n, 0, 0);
        
        return ans;
    }
};

• Time complexity : O(n4^n) 한번 호출에 최소 4개의 make_parentheses 함수가 호출되므로 O(4^n)그리고, stack을 이용하여 valid여부를 체크할 때 n만큼 소요됨으로 최종적으로 O(n4^n)이다.
• Space Complexity : O(n4^n) 공간도 함수 call stack과 검사를 위한 stack 모두 이용함으로 O(n4^n)이다. 

 

사실 Solution을 확인하면 더 멋진 방법이 있는 것 같은데, 이해가 잘 되지 않아 확인 중이다. 더 멋진 방법은 아래 링크의 Solution을 참고하라. 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/794/

Explore - LeetCode