[BOJ/Silver 1] 백준 25918 북극곰은 괄호를 찢어(C++)

문제 링크

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

25918번: 북극곰은 괄호를 찢어

 

문제

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

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

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

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

 

입력

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

N
S

 

출력

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

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

 

제한

•  1 ≤ N ≤ 200,000
•  S는 '(' 또는 ')'로 이루어져 있다.

 

예제 입력 1

6
()()()

예제 출력 1

1

예제 입력 2

10
(()))((())

예제 출력 2

2

예제 입력 3

3
(()

예제 출력 3

-1

 

알고리즘 분류

• 그리디 알고리즘

 

풀이

변수를 하나 선언한다.

여는 괄호가 등장하면 변수를 1 증가시키고 닫는 괄호가 등장하면 변수를 1 감소시킨다. 변수가 다시 0이 되면 북극곰이 O나 X를 하나 찢었다는 뜻이 된다.

변수의 값의 가장 큰 절댓값이 문자열을 만들 때 필요한 최소 일 수가 된다.

다만 모든 문자열을 다 탐색한 후 변수의 값이 0이 되지 않는다면 O나 X를 놓아서 해당 문자열을 만들 수 없다는 뜻이 되므로 -1을 출력한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
string S;
int Answer;

void input() {
    cin >> N;
    cin >> S;
}

void settings() {
    for (int i = 0; i < (int)S.size(); i++) {
        char Now = S[i];
        if (Now == '(') {
            M++;
        }
        else {
            M--;
        }
        Answer = max(Answer, abs(M));
    }
}

void find_Answer() {
    if (M == 0) {
        cout << Answer << "\n";
    }
    else {
        cout << "-1\n";
    }
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}