[Backtracking][Medium] 22. Generate Parentheses

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. n이 주어질때, n 쌍이 되도록 괄호를 open/close 규칙에 맞게 만들어라. 

 

 

Solution. 

 좋은 문제다. 

 풀이법을 반드시 숙지하면 좋다. 

 

 우선 한번의 문자를 추가할 시 두개의 옵션이 생긴다. 

  '(' 을 추가할 지, ')'를 추가할 지에 대한 옵션이 그것이다. 

  이 추가 연산을 n x 2 가 될때까지 단순히 수행하면 될 것이다. 

 다만, 괄호 규칙에 맞게 하라고 했으므로, 해당 문자열의 길이가 n x 2 일때 규칙에 부합하는지 확인하면 될 것이다. 

 

 위 풀이만으로도 해결은 될 것이다. 

 

 하지만 조금 더 나아가서 보면, 

 ')' 는 항상 문자열에서 '('의 개수가 더 많을때만 등장해야 함을 알 수 있다. 

 이것을 조금 더 선행해서 검사 해 주고, 마지막의 규칙 검사를 생략 할 수 있다. 

 

 이를 코드로 만들어 본다. 

 

void build_Parenthesis(vector<string>& vRet, string& strCombi, int n, int cntOpen, int cntClose)
{
    if (strCombi.size() == n * 2)
    {
        if (cntOpen == cntClose)
            vRet.push_back(strCombi);
        return;
    }

    // 1st Addition : ( 추가는 규칙이 필요 없다.
    strCombi += "(";
    build_Parenthesis(vRet, strCombi, n, cntOpen + 1, cntClose);
    strCombi.erase(strCombi.size()-1, 1);

    // 2nd Addition : ) 괄호 생성 조건을 추가 해 준다.
    if (cntOpen > cntClose)
    {
        strCombi += ")";
        build_Parenthesis(vRet, strCombi, n, cntOpen, cntClose + 1);
        strCombi.erase(strCombi.size() - 1, 1);
    }
}
vector<string> generateParenthesis(int n)
{ 
    vector<string> vRet;
    string strCurrent = "(";
    build_Parenthesis(vRet, strCurrent, n, 1, 0);
    return vRet;
}

 

잘 해결 되었음을 확인 할 수 있다. 

 

Note) Backtracking 은 기본적으로 많은 연산을 한다. 따라서 아래의 두가지 최적화가 같이 있으면 더욱 좋다. 

 - 특정 조건을 재귀 call 하기 전에 걸를 수 있다면 더욱 좋다. 

 - 인자는 reference나 pointer로 전달하면 복사 전달 보다 훨씬 빠르다.