순서

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


I. 문제

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

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

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

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

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

입력 설명

첫 번째 줄에 N개의 괄호 문자열이 입력된다 (1<= N <= 100,000, 짝수)
글자 하나가 잘못 입력된 문자열이나 정상 문자열이 입력된다.

출력 설명

하나의 괄호를 반대로 하면 전체가 균형 잡힌 문자열이 되도록 하는 위치의 수를 출력하시오

[입력]
()(())))

[출력]
4

[부가정보]
12345678
()(())))
2를 뒤집으면 (((()))), 5번을 뒤집으면 ()((()))
6번을 뒤집으면 ()(()()), 7번을 뒤집으면 ()(())()
총 4가지가 가능하다.

 


II. 접근

앞서 "균형 잡힌 괄호 문자열1" 문제와 같이 balance 변수를 활용한다.
"("이 나오면 balance++
")"이 나오면 balance--

하지만 이 문제에서는 뒤집을 수 있는 경우가 복수개가 나오므로 활용을 해야한다.

힌트는 단 1개만 뒤집는 것!


예외 1인 탐색 중 balance < 0 이 되는 경우가 발생한다면 그 뒤는 볼 것도 없다.
해당 경우가 발생할 때까지 포함하여 ')' 갯수가 답이기 때문이다.

ex) (  )  )  )   => -1가 나온 것 까지 ')' 의 수가 답 1개 
    1 0 -1 -2


예외 2인 탐색완료 후 balance > 0이 되는 경우가 발생한다면
탐색 시 balance >= 2 위치의 '(' 갯수가 답이다.

위와 마찬가지로 balance>0 일 때는 '(' 가 더 많으므로 ')' 로 바꿔주어야 하고 balance를 -2 해주어야 한다.

따라서 string의 중간에서 변경이 이루어지려면 아무런 영향이 없어야하기 때문에 balance >=2의 조건이 붙는다.

ex) (  )  (  (  (  ) => 2 이상의 '(' 의 갯수가 답 2 개
    1 0  1  2 3 2

하지만 여기서 예외가 있다.

ex) (  ) (  (  ) (  => 2 이상의 '('의 갯수가 답 2 개??
    1 0 1 2 1 2

위에서 한 가지 간과한 것은 balance가 -2가 될 때, 이후의 string에 모두 영향을 주는 것이다.
따라서 순차적으로 탐색하며 정답의 개수를 세주다가 balance가 1이하가 나오면 개수를 초기화 시켜줘야 한다.
(III. 구현 참고)

 


III. 구현

<hide/>
#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

string str;
int sol;

int solve(){

    int closecheck{ 0 }; // 예외 1 관련
	int opencheck{ 0 }; // 예외 2 관련
	int balance{ 0 };

    // string 순차적으로 탐색
	for (int i = 0; i < int(str.size()); i++) {
		if (str[i] == '(') {
			balance++;
			// 예외 2 관련 체크
			if (balance >= 2) opencheck++;
		}
		if (str[i] == ')') {
			balance--;
			closecheck++;
            
			// 예외 1 관련, 걸리면 break로 끝냄
			if (balance < 0) return closecheck;
		}
        
		// balance가 2보다 작을 때 예외 2 관련 0으로 초기화
        // 그 전에서 '(' 를 뒤집으면 영향받아 0 미만으로 되어 균형이 깨짐
		if (balance < 2) opencheck = 0;
	}
    return opencheck;
}

int main() {
	cin >> str;
    
	sol = solve()
	
	printf("%d", sol);
	return 0;
}

+ Recent posts