C++에서 인접 문자 교체 및 제거로 구하는 균형 괄호 문자열의 최대 길이

문제 개요

(,),{},[] 여섯 종류의 괄호 문자만으로 구성된 문자열이 주어집니다. 목표는 인접한 문자를 서로 교체하거나 불필요한 문자를 제거하여 문자열 전체가 균형 상태가 되도록 만들 때, 얻을 수 있는 균형 문자열의 최대 길이를 구하는 것입니다.

인접한 두 문자가 서로 반대 방향의 짝이라면 자유롭게 교체할 수 있습니다. 예를 들어 }{, )(][ 는 맞바꿀이 가능하지만, {{, ((, [[}}, ))]]처럼 같은 방향의 문자끼리는 교체할 수 없습니다.

또한 짝을 이루지 못한 문자는 제거할 수도 있습니다. 예를 들어 “{{}][” 에서 첫 번째 { 를 제거하면 “{}[]” 가 되어 균형 문자열의 길이는 4가 됩니다.

입력 · 출력 예시

예시 1

입력:

str[] = “{{{}}{]]][()”  (길이 12)

출력:

균형 문자열의 최대 길이: 8

설명: str[0]과 str[1]은 교체할 수 없으므로 str[0]을 제거해 “{{}}{]]][()”를 만듭니다. 이어서 str[1]과 str[2]도 교체할 수 없으므로 str[1]을 제거해 “{}}{]]][()”를 만듭니다. 이후 {}는 이미 균형을 이루고}{는 교체 가능하며]] 두 개는 제거하고][는 교체하고, () 역시 균형을 이룹니다. 최종 문자열은 {}{}[]()이며 길이는 8입니다.

예시 2

입력:

str[] = “(((((()”  (길이 7)

출력:

균형 문자열의 최대 길이: 2

설명: str[5]와 str[6]만 균형을 이루므로 나머지 문자는 모두 제거합니다. 최종 문자열은 ()이며 길이는 2입니다.

알고리즘 접근 방식

문자 배열 str[]에 원본 문자열을 저장하고, 정수 변수 len에 문자열의 길이를 저장합니다.
maxBalancedStr(char str[], int len) 함수는 문자열과 그 길이를 매개변수로 받아 균형 문자열의 최대 길이를 반환합니다.
변수 count는 균형 문자열의 길이를 저장하며, 초기값은 0입니다.
문자열의 첫 문자부터 순회하면서 인접한 두 문자가 교체 시 균형을 이루는지, 혹은 이미 균형인지 확인합니다. 해당하는 경우 count를 2씩 증가시킵니다.
(), )(, {}}{, []][ 와 같은 쌍이 발견되면 count를 2 증가시키고 i도 함께 증가시켜 다음 문자로 건너뜁니다.
순회가 끝나면 count에 균형 문자열의 길이가 저장되며, 이 값을 결과로 반환합니다.

이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리는 상수 수준(O(1))으로 매우 효율적입니다.

C++ 구현 예제

// 괄호 문자열 처리를 위한 C++ 구현
#include <bits/stdc++.h>
using namespace std;

// 가장 긴 균형 문자열의 길이를 반환하는 함수
int maxBalancedStr(char str[], int len){
    int count = 0;
    // 문자열을 처음부터 끝까지 순회
    for (int i = 0; i < len; i++) {
        // 소괄호 쌍 확인 (교체 가능)
        if ((str[i]=='(' && str[i+1]==')') || (str[i]==')' && str[i+1]=='(')) {
            count += 2; ++i;
        }
        // 중괄호 쌍 확인 (교체 가능)
        else if ((str[i]=='{' && str[i+1]=='}') || (str[i]=='}' && str[i+1]=='{')) {
            count += 2; ++i;
        }
        // 대괄호 쌍 확인 (교체 가능)
        else if ((str[i]=='[' && str[i+1]==']') || (str[i]==']' && str[i+1]=='[')) {
            count += 2; ++i;
        }
    }
    return count;
}

// 드라이버 코드
int main(){
    char str[] = ")([]]((";
    int length = 7;
    cout << maxBalancedStr(str, length);
    return 0;
}

실행 결과

입력 문자열 “)([]](” 의 경우, 앞의 )( 는 교체하여 () 로 만들 수 있고, 이어지는 [] 는 이미 균형을 이루고 있습니다. 따라서 최종적으로 ()[] 형태의 균형 문자열을 얻을 수 있으며 그 길이는 4입니다.

마무리

이 문제는 일반적인 스택 기반 유효 괄호 검사와 비슷해 보이지만, 인접 문자 교체가 허용된다는 조건 덕분에 단순히 옆 문자와의 짝 여부만 확인하는 선형 탐색으로 해결할 수 있습니다. 문자열 순회와 조건 분기만으로 깔끔하게 구현할 수 있어 코딩 테스트에서 자주 등장하는 기초 유형 중 하나입니다.