취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24552번 문제인 올바른 괄호이다.
문제는 아래 링크를 확인하자.

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

괄호를 하나 지워서 올바른 괄호열을 만들 수 있는 문자열은 '('와 ')'의 개수가 정확히 하나 차이가 난다. 따라서 먼저 주어진 괄호열에서 '('이 많은지 ')'이 많은지를 확인한 후, 더 많은 쪽을 하나 지워야 할 것이다.

편의상 '('의 개수가 하나 더 많다고 가정하자.

적어도 하나의 '('에 대해서 해당 괄호를 지웠을 때 이 문자열이 올바른 괄호열이 될 수 있으므로, 문자열을 처음서부터 읽기 시작하여 어떤 지점까지의 문자열이 올바른 부분괄호열이었다면 원래의 문자열에서 해당 부분괄호열의 위치에 대응되는 '(' 하나를 지우면 절대 올바른 괄호열을 얻을 수 없게 되는 점을 관찰하는 것으로 문제를 해결하자.

')'의 경우, 문자열을 뒤에서부터 읽는 것으로 '('의 경우와 같은 방식으로 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int cnt[128];

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

	string s; cin >> s;
	for (auto l : s) cnt[l]++;
	if (cnt['('] > cnt[')']) {
		int ans = 0, total = 0;
		for (auto l : s) {
			if (l == '(') {
				ans++, total++;
			}
			else {
				total--;
				if (total == 0) ans = 0;
			}
		}

		cout << ans;
	}
	else {
		reverse(s.begin(), s.end());
		int ans = 0, total = 0;
		for (auto l : s) {
			if (l == ')') {
				ans++, total++;
			}
			else {
				total--;
				if (total == 0) ans = 0;
			}
		}

		cout << ans;
	}
}