[백준] 4889번 : 안정적인 문자열(JAVA)

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

4889번: 안정적인 문자열

풀이

"-"가 포함한 문자가 나오기 전까지 입력받은 괄호들이 올바른 괄호가 될때까지의 최소의 돌리는 시간을 구하는 문제입니다.

ex) {{ --> {} 1번

}{}{ --> {{}} 2번

}}{{ --> {}{} 2번

 

입력받은 문자를 1글자씩 비교하면서 진행하시면 됩니다.

{가 들어왔을 경우에는 stack에 넣어주고, }이 들어왔을 경우 stack이 비어있으면 stack에 {를 넣어주고 값을 더해주면 됩고, 아닐경우 stack에서 {를 빼주면 됩니다.

최종적으로 마무리되었을 경우 스택의 크기 / 2 + 더해준 값을 해주면 됩니다.

여기서 스택의 크기 / 2를 하는 이유는 스택에 {{과 같이 들어있을 경우 {} 로 1번만 돌려주면 되서 /2의 값을 더해줍니다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
	
		StringBuilder sb = new StringBuilder();
		int count = 1;
		while(true) {
			String s = br.readLine();
			
			if(s.contains("-")) {
				break;
			}
			
			Stack<Character> stack = new Stack<>();
			
			int answer = 0;
			for(char ch : s.toCharArray()) {
				if(ch == '{') {
					stack.add(ch);
				}
				else {
					if(stack.isEmpty()) {
						answer++;
						stack.add('{');
					}
					else {
						stack.pop();
					}
				}
			}
			sb.append(count).append(". ").append(answer + (stack.size() / 2)).append("\n");
			count++;
		}
		System.out.print(sb);
	}
}