[BOJ] 25918번_북극곰은 괄호를 찢어_스택 (C++)

[문제]

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

입력받은 N의 길이의 괄호로 이루어진 S문자열을 만드는 문제. 하루에 한 번 O는 ()로 X는 )(로 바꿀 수 있는데 이를 이용해서 문자열을 만드는데 최소 며칠 걸리는지 구하는 문제이다.

[사용 알고리즘]

스택

[풀이 핵심]

1. N의 크기만큼 for문을 돌면서 입력받은 문자열을 확인한다.
2. 스택이 비어있으면

• 문자열의 i번째 문자를 push해준다.

3. 스택이 비어있지 않으면

• 문자열의 i번째 문자가 '(' 이면서 스택의 top이 ')' 이면 pop해준다.
• 문자열의 i번째 문자가 ')' 이면서 스택의 top이 '(' 이면 pop해준다.
• 둘다 아닐 경우에 문자열의 i번째 문자를 push해준다.

4. 스택의 최대 크기는 걸리는 날짜이므로 스택 크기의 max값을 계속 갱신해준다.
5. for문이 끝나고 스택에 값이 남아있으면 만들 수 없는 문자열이므로 -1을 출력한다.

[코드]

//boj25918번_북극곰은 괄호를 찢어_스택

#include<iostream>
#include<stack>

using namespace std;

int main() {
	int N;
	string str;

	cin >> N;
	cin >> str;

	stack<int> s;

	int result = 0;

	for (int i = 0; i < N; i++) {
		if (s.empty()) {
			s.push(str[i]);
		}
		else {
			if (str[i] == '(' && s.top() == ')') {
				s.pop();
			}
			else if (str[i] == ')' && s.top() == '(') {
				s.pop();
			}
			else {
				s.push(str[i]);
			}
		}
		result = max(result, (int)s.size());
	}

	if (s.empty()) {
		cout << result;
	}
	else {
		cout << -1;
	}
}