백준 : 4889 안정적인 문자열

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

4889번: 안정적인 문자열

 

1. stack이 비웠고 '}' 문자열이면 cnt+1 하고 stack에 바꾼 '{' 를 push

 

2. stack 이 비지않았고 '}' 만나면 stack pop

 

3. 나머지는 stack에 '{' push

 

모든 문자열을 탐색하고나서 stack에 쌓인 사이즈의 절반은 cnt에 더해주면 된다.

 

이게 가능한 이유를 생각해보자.

 

 

1. 바꾸는 경우는 '{' 와 '}' 밖에 없다. stack은 괄호가 제대로 닫혀있는지 판단한다. 이때 stack에 비어있는데 닫히는 괄호가 들어오면 지금의 문자는 무조건 change 해야한다.

 

2. stack에 1의 조건과 같이 추가한다면 stack.에는 여는 괄호만 쌓인다 이때 닫히는 괄호를 만나면 pop을 해줄수 있다.

 

3. 1 , 2 의 조건으로 모두쌓으면 stack에는 아무것도없거나 여는 괄호만 쌓이게된다. 이때 여는 괄호들을 알맞은 쌍으로 해주기위해서 절반은 '}' 문자로 바꿔주면 된다.

 

소스코드

package ps;

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

public class 안정적인문자열 {
	static Stack<Character> stack;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1;; t++) {
			char[] str = br.readLine().toCharArray();
			int ans = 0;
			stack = new Stack<Character>();
			if (str[0] == '-')
				break;

			for (int i = 0; i < str.length; i++) {
				if (stack.isEmpty() && str[i] == '}') {
					stack.add('{');
					ans++;
				} else if (str[i] == '}') {
					stack.pop();
				} else {
					stack.add('{');
				}
			}

			ans += stack.size() / 2;
			sb.append(t).append('.').append(' ').append(ans).append('\n');
		}
		System.out.println(sb.toString());
	}
}