[Silver I] 북극곰은 괄호를 찢어-25918

[문제 위치]

https://www.acmicpc.net/problem/25918

[문제 풀이]

이 코드는 주어진 괄호 문자열이 올바르게 짝을 맞출 수 있는지 확인하고, 그 과정에서 필요한 최대 깊이(불균형 정도)를 계산한다.

1. 문자열 길이가 홀수거나 입력된 길이가 맞지 않으면 애초에 올바른 괄호열이 될 수 없으므로 -1을 출력한다.
2. 문자열을 왼쪽부터 탐색하면서 '('를 만나면 balance를 1 증가, ')'를 만나면 1 감소시킨다.
3. 이때 balance의 절댓값이 지금까지 나온 최대값을 갱신한다. 이는 괄호가 얼마나 한쪽으로 치우쳤는지를 의미한다.
4. 모든 탐색이 끝난 후 balance가 0이라면 괄호 개수가 맞아떨어진 것이고, 그때 최대 절댓값을 출력한다. 만약 balance가 0이 아니라면 짝이 맞지 않으므로 -1을 출력한다.

즉, 결과는 올바른 괄호열일 때 그 문자열이 중간에 가장 불균형했던 깊이를 나타내며, 불가능한 경우 -1을 반환한다.

 

아래는 이를 구현한 코드이다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string s;
    cin >> s;

    // 길이가 홀수면 불가능
    if (n % 2 == 1 || (int)s.size() != n) {
        cout << -1 << "\n";
        return 0;
    }

    int balance = 0;
    int max_abs = 0;

    for (char ch : s) {
        if (ch == '(') balance++;
        else balance--;
        if (abs(balance) > max_abs) max_abs = abs(balance);
    }

    // 최종 균형이 맞지 않으면 불가능
    if (balance != 0) cout << -1 << "\n";
    else cout << max_abs << "\n";

    return 0;
}