input으로 들어온 숫자만큼 괄호를 열고 닫는 방법의 모든 조건을 내보내면 되는 문제이다.


1 -> ()

2 -> (()), ()()


이런 식이다.



void makeParenthesis(vector<string> &tRet, int &nCount, int &nOpen, int &nClose, string str)

{

    if( nOpen < nCount )

    {

        str += '(';

        ++nOpen;

        makeParenthesis(tRet, nCount, nOpen, nClose, str);

        str.pop_back();

        --nOpen;

    }

    

    if( nClose < nOpen && nClose < nCount )

    {

        str += ')';

        ++nClose;

        makeParenthesis(tRet, nCount, nOpen, nClose, str);

        str.pop_back();

        --nClose;

    }

    

    if( nOpen == nCount && nClose == nCount )

        tRet.push_back(str);

}


vector<string> generateParenthesis(int n)

{

    vector<string> tRet;

    string str;

    int nOpen = 0;

    int nClose = 0;

    

    makeParenthesis(tRet, n, nOpen, nClose, str);

    

    return tRet;

}



다른 사람들의 풀이 방법도 보기는 했는데, 확실히 코드 양은 줄여져 있지만, 기본적인 원리는 동일하다.

간만에 리트코드 풀어본 기분이 든다.

'Programming > C,C++' 카테고리의 다른 글

[LeetCode] 34. Search for a Range  (0) 2018.01.26
[LeetCode] 33. Search in Rotated Sorted Array  (0) 2018.01.26
[LeetCode] 22. Generate Parentheses  (0) 2018.01.25
[BOJ] 10844. 쉬운 계단 수  (0) 2018.01.21
[BOJ] 1149. RGB거리  (0) 2018.01.20
[BOJ] 1932. 숫자삼각형  (0) 2018.01.19

+ Recent posts