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

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

4889번: 안정적인 문자열

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack;

        int tc = 1;
        while(true){
            String input = br.readLine();
            stack = new Stack<>();
            int cnt = 0;
            if(input.contains("-")){
                break;
            }
            for(int i=0;i<input.length();i++){
                char tmp = input.charAt(i);
                switch (tmp){
                    case '{':
                        stack.push('{');
                        break;
                    case '}':
                        if(stack.isEmpty()){
                            stack.push('{');
                            cnt++;
                        }
                        else{
                            stack.pop();
                        }
                }
            }
            int answer = 0;
            answer = stack.size()/2 + cnt;

            System.out.println(tc+". "+answer);
            tc++;

        }

    }
}

괄호 문제는 Stack을 사용한다.

1. '{' 라면 stack에 push

2. '}' 라면

2-1. stack이 비어있는지 확인하고 비어있다면 '{'로 바꾸고 stack push, cnt++

2-2. 비어있지 않다면 '{'가 있다는 것이므로 stack.pop

3. 모든 문자를 검사하고 나면 stack에 남아있는 문자들은 모두 {일 것이다. 이 때 {중 하나만 }로 바꾸면 안정적 문자열이 되는 것이므로 stack.size() /2를 하면 된다.

4. stack에 넣을 때 바꾼 횟수인 cnt와 stack.size()/2를 더하면 정답이 된다.