[Java] 백준 4889번 : 안정적인 문자열

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

예제 입력 1

}{
{}{}{}
{{{}
---

예제 출력 1

1. 2
2. 0
3. 1

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	private static Stack<Character> stack;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		String s="";
		int t=0;
		while((s=br.readLine()).charAt(0)!='-') {
			t++;
			stack=new Stack<>();
			int cnt=0;
			for(int i=0;i<s.length();i++) {
				if(s.charAt(i)=='{') {	// '{'이면 스택에 추가
					stack.add('{');
				} else {
					if(stack.isEmpty()) {	// '}'이고 스택에 짝이 없으면 '{'로 변경하여 스택에 추가
						cnt++;
						stack.add('{');
					}
					else stack.pop();	// '}'이고 스택에 짝이 있으면 짝을 스택에서 pop
				}
			}
			cnt+=stack.size()/2;	// 스택에 남은 문자들의 절반을 뒤집어서 서로 짝으로 만들어줌
			System.out.println(t+". "+cnt);
		}
	}

}

여는 괄호( '{' )이면 스택에 추가하고, 닫는 괄호( '}' )이면 스택에서 pop을 해줍니다. 단, 스택에 짝이 없는 경우 닫는 괄호를 여는 괄호로 변경하고, 마지막에 스택에 값이 남는 경우 남은 값의 절반을 닫는 괄호로 변경하여 짝을 만들어줍니다.