C++로 최소 괄호 삽입 횟수 구하기: 균형 잡힌 괄호 문자열 만들기

이번 글에서는 '(' 와 ')' 두 종류의 괄호만으로 이루어진 문자열 s가 주어졌을 때, 이 문자열을 균형 잡힌(balanced) 상태로 만들기 위해 삽입해야 하는 괄호의 최소 개수를 구하는 방법을 알아보겠습니다.

여기서 균형 잡힌 문자열이란 모든 여는 괄호 '('에 대응하는 닫는 괄호 ')'가 올바른 순서로 짝지어져 있는 문자열을 의미합니다.

문제 예시

예를 들어, 입력 문자열이 "(()))("라고 가정해 보겠습니다. 이 경우 정답은 2입니다.

"(()))(" 는 괄호를 두 개만 추가하면 다음과 같이 균형 잡힌 문자열로 만들 수 있기 때문입니다.

"((()))()"

해결 접근 방식

이 문제는 그리디(greedy) 기법과 두 개의 카운터를 사용하면 선형 시간 안에 해결할 수 있습니다.

o: 아직 짝을 찾지 못한 여는 괄호 '('의 개수
cnt: 매칭에 실패한 닫는 괄호 ')'의 개수, 즉 앞에 새로운 '('를 삽입해야 하는 횟수

구체적인 알고리즘 단계는 다음과 같습니다.

o = 0, cnt = 0으로 초기화합니다.
문자열의 처음부터 끝까지 한 글자씩 탐색합니다.
- 현재 문자가 '('이면 o를 1 증가시킵니다.
- 현재 문자가 ')'라면:
  - o가 0이 아니면 대응되는 여는 괄호가 있다는 뜻이므로 o를 1 감소시킵니다.
  - o가 0이면 매칭할 여는 괄호가 없으므로 cnt를 1 증가시킵니다.
탐색이 끝나면 cnt + o를 반환합니다. 이 값이 곧 삽입해야 할 최소 괄호 개수입니다.

동작 원리

이 알고리즘이 작동하는 이유는 간단합니다. 문자열을 왼쪽에서 오른쪽으로 훑으면서, 여는 괄호가 나오면 일단 저장해 두고(o++), 닫는 괄호가 나오면 저장해 둔 여는 괄호와 즉시 매칭합니다(o--). 만약 매칭할 여는 괄호가 없다면 해당 위치 앞에 새로운 '('를 삽입해야 하므로 cnt를 증가시킵니다.

모든 문자를 처리한 후에도 o에 값이 남아 있다면, 이는 끝까지 짝을 찾지 못한 여는 괄호들이므로 각각에 대해 ')'를 삽입해야 합니다. 따라서 최종 답은 cnt + o가 됩니다.

C++ 구현 코드

아래 예제 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(string s) {
      int o = 0;
      int cnt = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] == '('){
            o++;
         } else {
            if(o)
               o--;
            else
               cnt++;
         }
      }
      return cnt + o;
   }
};
int main(){
   Solution ob;
   cout << (ob.solve("(()))("));
}

실행 결과

입력

"(()))("

출력

복잡도 분석

시간 복잡도: O(n) — 문자열을 단 한 번만 순회합니다.
공간 복잡도: O(1) — 추가 자료구조 없이 두 개의 정수 변수만 사용합니다.