문제 소개
이 튜토리얼에서는 괄호 문자열의 균형을 맞추는 데 드는 최소 비용을 구하는 C++ 프로그램을 살펴보겠습니다.
여기서 '비용'이란 괄호를 한 칸씩 이동시키는 횟수를 의미합니다. 여는 괄호 '(' 와 닫는 괄호 ')' 로 구성된 문자열이 주어졌을 때, 괄호들의 위치를 적절히 이동시켜 전체 문자열이 올바른 괄호 식이 되도록 만들어야 합니다. 만약 여는 괄호와 닫는 괄호의 개수가 달라 균형을 맞추는 것이 아예 불가능하다면 -1을 반환합니다.
알고리즘 접근 방식
핵심 아이디어는 접두사 합(prefix sum)을 활용하는 것입니다.
- 여는 괄호 '(' 를 만나면 누적 값에 +1을 하고, 닫는 괄호 ')' 를 만나면 -1을 합니다.
- 왼쪽에서 오른쪽으로 스캔하면서 누적 값이 음수가 되는 순간마다, 그 절댓값만큼을 비용에 더합니다. 이는 그 시점까지 닫는 괄호가 초과했다는 의미이며, 초과분만큼 괄호를 뒤로 밀어야 하기 때문입니다.
- 스캔이 끝난 후 누적 값이 0이 아니면(즉, 두 괄호의 개수가 다르면) 균형을 맞출 수 없으므로 -1을 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int costToBalance(string s) {
if (s.length() == 0)
cout << 0 << endl;
// 여는 괄호와 닫는 괄호의 개수 저장
int ans = 0;
int o = 0, c = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(')
o++;
if (s[i] == ')')
c++;
}
// 개수가 다르면 균형 불가능
if (o != c)
return -1;
int a[s.size()];
if (s[0] == '(')
a[0] = 1;
else
a[0] = -1;
if (a[0] < 0)
ans += abs(a[0]);
for (int i = 1; i < s.length(); i++) {
if (s[i] == '(')
a[i] = a[i - 1] + 1;
else
a[i] = a[i - 1] - 1;
if (a[i] < 0)
ans += abs(a[i]);
}
return ans;
}
int main() {
string s;
s = ")))(((";
cout << costToBalance(s) << endl;
s = "))((";
cout << costToBalance(s) << endl;
return 0;
}실행 결과
9 4
결과 분석
첫 번째 입력 ")))(((" 의 경우, 접두사 합은 순서대로 -1, -2, -3, -2, -1, 0이 됩니다. 음수가 되는 지점마다 절댓값을 더하면 1 + 2 + 3 + 2 + 1 = 9가 되어 총 비용은 9입니다.
두 번째 입력 "))((" 의 경우, 접두사 합은 -1, -2, -1, 0이 되므로 1 + 2 + 1 = 4, 즉 총 비용은 4입니다.
이처럼 접두사 합 배열 하나만으로 각 위치에서의 불균형 정도를 추적할 수 있으며, 전체 시간 복잡도는 O(n)으로 매우 효율적으로 문제를 해결할 수 있습니다.