C++에서 유효한 괄호 문자열을 만들기 위해 추가해야 할 최소 괄호 개수

문제 설명

여는 괄호 '('와 닫는 괄호 ')'로만 이루어진 문자열이 주어집니다. 이 문자열에 괄호를 최소한으로 추가하여 결과 문자열이 유효한(valid) 괄호 문자열이 되도록 만들어야 합니다. 유효한 괄호 문자열이란 모든 여는 괄호가 자신과 짝을 이루는 닫는 괄호를 가지며, 그 순서도 올바른 경우를 의미합니다.

예시

예를 들어 str = "((()" 라면, 문자열 끝에 닫는 괄호 2개 '))'를 붙여야 하므로 필요한 괄호의 최소 개수는 2입니다.

접근 방법

단순히 여는 괄호와 닫는 괄호의 개수 차이(abs)만 계산하는 방법도 있지만, 이 방식은 ")("처럼 순서가 잘못된 경우를 처리하지 못합니다. 실제로 ")("에는 괄호 2개가 필요하지만 개수 차이는 0이 되기 때문입니다. 따라서 문자열을 한 번 순회하면서 균형 상태를 추적하는 방식이 더 정확하고 안전합니다.

• 문자를 왼쪽에서 오른쪽으로 하나씩 확인합니다.
• 여는 괄호 '('를 만나면 아직 짝을 찾지 못한 여는 괄호 카운터(open)를 1 증가시킵니다.
• 닫는 괄호 ')'를 만나면 매칭할 수 있는 여는 괄호가 있으면(open > 0) open을 1 감소시키고, 없다면 앞에 여는 괄호를 추가해야 하므로 필요한 괄호 카운터(closeNeeded)를 1 증가시킵니다.
• 순회가 끝나면 정답은 open + closeNeeded입니다. open은 뒤에 추가해야 할 닫는 괄호 수, closeNeeded는 앞에 추가해야 할 여는 괄호 수를 나타냅니다.

C++ 구현

#include <iostream>
#include <string>
using namespace std;

int minAddToMakeValid(string str) {
    int open = 0;         // 아직 짝을 찾지 못한 여는 괄호 수
    int closeNeeded = 0;  // 앞에 추가해야 하는 여는 괄호 수
    for (char c : str) {
        if (c == '(') {
            ++open;
        } else if (c == ')') {
            if (open > 0) {
                --open;          // 기존 여는 괄호와 매칭
            } else {
                ++closeNeeded;   // 새 여는 괄호 필요
            }
        }
    }
    return open + closeNeeded;
}

int main() {
    string str = "((()";
    cout << "필요한 괄호 수 = " << minAddToMakeValid(str) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 출력이 생성됩니다.

필요한 괄호 수 = 2

복잡도 분석

• 시간 복잡도: O(n) — 문자열을 한 번만 순회합니다.
• 공간 복잡도: O(1) — 두 개의 정수 카운터만 사용하므로 추가 메모리가 거의 필요하지 않습니다.