[Algorithm][String] 균형 잡힌 괄호 문자열1

순서

I. 문제
II. 접근
III. 구현

---

I. 문제

균형 잡힌 문자열이 될 수 있도록 뒤집어야 하는 (예를들어, 오른쪽 괄호를 왼쪽 괄호로, 또는 왼쪽 괄호를 오른쪽 괄호로 변경) 괄호 문자의 최소 수를 계산하여라

균형 잡힌 괄호 문자열이 되려면 '('의 수와')'의 수가 반드시 동일해야 하고, ')' 앞에 '('가 많거나 같은 수가 있어야 한다.

예를 들어, 다음의 문자열은 모두 균형 잡힌 괄호 문자열이다.

()
(())
()(()())

아래 문자열은 균형 잡힌 괄호 문자열이 아니다
)(
())(
((())))

입력 설명

첫 번째 줄에 N개의 괄호 문자열이 입력된다 (1<= N <= 100,000, 짝수)

출력 설명

균형 잡힌 문자열이 될 수 있도록 뒤집어야 하는 괄호 문자의 최소 수를 출력하시오

[입력]
())(

[출력]
2

[부가정보]
1234
())(
4번 괄호는 무조건 뒤집고, 2와 3번 괄호 중 하나를 뒤집어야 한다.

---

II. 접근

괄호가 완벽해지는 조건을 생각하기보다 예외를 생각하는 것이 빠르다.

예외 1. "(" 보다 ")"가 먼저 나왔을 때. ex) ()), (()()))
예외 2. 완성 했지만 "("의 수가 더 많을 때,
예외 3. 완성 했지만 ")"의 수가 더 많을 때 ->예외 1과 동일

그러면 예외를 어떻게 처리해야 할까?

string을 받은 이후에 string[0] 부터 string[N-1] 까지 쭉 보면서 단계마다 검토한다.
이때 검토를 하기 위한 변수 int balance를 정의한다.

순서는 다음과 같다.

1. "(" 가 나오면 balance++
2. ")" 가 나오면 balance--

3. 탐색 중 balance < 0 이라면 balance = 1 : 올바르게 뒤집어 줌. (예외 1 처리)
4.  완성 후 balance > 0 이라면 ans += balance/2 : 마지막 괄호의 수 동일하게 만들어 줌.

대부분의 "균형 잡힌 괄호 문자열" 문제는 balance 변수를 이용한 풀이를 사용한다.

 

---

III. 구현

<hide/>
#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

string str;
int swapnum; // 최종 답안
int balance; // balance

void input() {
	cin >> str;
}

void solve() {
    //string을 쭉 돌면서
	for (int i = 0; i < int(str.size()); i++) {
		
        // 매 괄호마다 검토
        if (str[i] == '(') balance++;
		else balance--;

        //예외처리 1
		if (balance < 0) {
			swapnum++;
			balance = 1;
		}
	}
    
    // 예외처리 2
	if (balance > 0) swapnum += balance / 2;
}

int main() {
	input();
	swapnum = 0;
	balance = 0;
	
	solve();

	cout << swapnum;

	return 0;
}