[BOJ] 북극곰은 괄호를 찢어 25918번 C++

문제

극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 O와 X를 보면 ()와 )(로 찢어버린다는 것이다.

협이는 이러한 북극곰의 특성을 이용하여 길이 N의 괄호 문자열 S를 만들고자 한다. 북극곰은 낮에 활동을 하기 때문에 낮에 돌아다니는 것은 위험하다. 때문에 협이는 매일 밤마다 활동할 수 있다. 밤에 협이는 문자열이 있으면 그 위에 O 또는 X를 원하는 만큼 놓을 수 있다. 그러면 낮에 북극곰이 와서 문자들을 모두 찢어 놓는다.

예를 들어 이미 문자열 ()()가 있다고 생각해보자. 밤에 문자를 (O)X(O) 다음과 같이 놓아둔다면 하루가 지나 (()))((())와 같은 문자열이 된다.

이때 원하는 문자열을 만들려면 최소 며칠이 걸리는지 계산해보자.

입력

입력은 아래와 같이 주어진다.

 N

 S

출력

원하는 문자열을 만들기 위해 걸리는 최소 일수를 구하라.

원하는 문자열을 만들 수 없다면 -1을 출력한다.

 

접근 방식

 

괄호의 깊이가 곧 필요한 일수와 같다 예를 들어 (())는 최대 깊이가 2이므로 2일이 필요!

따라서, depth 변수에 현재 괄호의 길이를 추적해주는데

(를 만나면 depth를 1증가, )를 만나면 1감소시킨다

 

이후 depth에 따라 최대 깊이를 기록하는데 이 때, ) 괄호가 먼저 나와 깊이가 음수일 수 있으므로 depth를 절댓값으로 처리해준다!

 

모든 문자 처리후에 depth가 0이 아니면 쌍이 맞지 않는 것이므로 -1을 출력하고

그렇지 않다면 최대 depth를 출력하면 된다!

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; 
    cin >> N;
    string S; 
    cin >> S;
    
    int depth = 0; 
    int max_depth = 0; 
    
    for (char c : S) {
        if (c == '(') {
            depth++;
        } else {
            depth--;
        }
        
        max_depth = max(max_depth, abs(depth));
    }

    if (depth != 0) { // 괄호쌍이 맞지 않는 경우
        cout << -1;
    } else {
        cout << max_depth;
    }
    
    return 0;
}