[백준 - 4889] 실버1 - 안정적인 문자열(그리디)

www.acmicpc.net/problem/4889

4889번: 안정적인 문자열

1. 유형

그리디

 

2. 풀이

스택을 이용한 그리디 문제이다.

 

'{'이 나오면 바로 push를 한다.

 

'}' 이 나올때마다 스택이 비어있지 않으면 pop을 해주고 비어있으면 push를 해준다. 

 

맨 처음에 '}' 이 나오면 '{'으로 바꿔주는 것이 핵심이다.

 

3. 코드

package 문자열;

import java.util.Scanner;
import java.util.Stack;

public class back_4889안정적인_문자열 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int idx=1;
		while (true) {
			Stack<Character> s = new Stack<>();
			String str = sc.nextLine();
			int total=0;
			if(str.charAt(0)=='-') break;
			for (int i = 0; i < str.length(); i++) {
				if(str.charAt(i)=='{') {
					s.add('{');
				}else {
					if(!s.empty()) {
						s.pop();
					}else {
						total++;
						s.add('{');
					}
				}
			}
			total+=(s.size()/2);
			System.out.println(idx+". "+total);
			idx++;
		}
	}
}