C++로 길이 2n의 유효한 괄호 시퀀스 n개 생성하기

숫자 n이 주어졌을 때, 정확히 n개의 서로 다른 유효한 괄호 시퀀스를 구하는 문제입니다. 여기서 괄호 시퀀스(bracket sequence)란 문자 '('와 ')'만으로 이루어진 문자열을 의미합니다.

그리고 유효한(valid) 괄호 시퀀스란, 원래 문자열의 문자들 사이에 '1'과 '+'를 삽입했을 때 올바른 산술 표현식으로 변환될 수 있는 시퀀스를 말합니다. 예를 들어 "()()"는 "(1)+(1)"처럼 만들 수 있으므로 유효한 시퀀스입니다.

즉, 주어진 숫자 n으로부터 길이가 2n인 서로 다른 유효한 괄호 시퀀스를 정확히 n개 출력해야 합니다.

예를 들어 입력이 n = 4라면, 출력은 다음과 같습니다.

["()()()()", "(())()()", "((()))()", "(((())))"]

해결 접근 방법

이 문제는 간단한 반복문 패턴으로 해결할 수 있습니다. 핵심 아이디어는 k번째 줄에서 앞부분에 중첩된 괄호 쌍 k개를 만들고, 뒷부분은 단순한 '()' 쌍으로 채우는 것입니다. 이렇게 하면 k 값마다 고유하면서도 모두 유효한 시퀀스가 자연스럽게 생성됩니다.

의사 코드(pseudo code)로 나타내면 다음과 같습니다.

for k = 1 부터 n 까지 반복:
    for i = 1 부터 k 까지 반복:
        "(" 출력
    for i = 1 부터 k 까지 반복:
        ")" 출력
    for i = k + 1 부터 n 까지 반복:
        "()" 출력
    줄바꿈

C++ 구현 예제

아래는 위 알고리즘을 실제로 구현한 C++ 코드입니다.

#include <bits/stdc++.h>
using namespace std;

void solve(int n) {
    for (int k = 1; k <= n; k++) {
        // 중첩된 여는 괄호 k개 출력
        for (int i = 1; i <= k; i++)
            cout << "(";
        // 중첩된 닫는 괄호 k개 출력
        for (int i = 1; i <= k; i++)
            cout << ")";
        // 남은 단순 괄호 쌍 출력
        for (int i = k + 1; i <= n; i++)
            cout << "()";
        cout << endl;
    }
}
int main() {
    int n = 4;
    solve(n);
}

입력

출력

()()()()
(())()()
((()))()
(((())))

동작 원리 설명

n = 4일 때 각 단계별 결과를 살펴보면 다음과 같습니다.

k = 1: 중첩 괄호 1쌍 + 단순 쌍 3개 → "()()()()"
k = 2: 중첩 괄호 2쌍 + 단순 쌍 2개 → "(())()()"
k = 3: 중첩 괄호 3쌍 + 단순 쌍 1개 → "((()))()"
k = 4: 중첩 괄호 4쌍 → "(((())))"

각 시퀀스의 길이는 정확히 2n이며, 모든 시퀀스는 '1'과 '+'를 삽입했을 때 올바른 산술식이 되므로 유효합니다. 또한 k 값이 서로 다르기 때문에 생성된 n개의 시퀀스는 모두 고유합니다. 이 알고리즘의 시간 복잡도는 O(n²)로 매우 효율적입니다.