백준 안정적인 문자열 4889 java

문제링크

문제 접근

• 괄호 문제는 스택을 쓰자
• 특정 규칙으로 만드는게 아니라 몇 번 수정하면 되는지가 궁금
• '{'는 스택 add
• '}'는 스택 peek()이 짝이 맞으면 poll(), 안맞으면 '{'로 바꾸고 add
• 문자열 다 돌았는데 스택이 남아있으면 {{{{{{이렇게 있는 것
• 그럼 스택 size / 2 만큼 바꾸면 해결

코드

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

public class baek_4889 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int turn = 1;
        while(true){
            st = new StringTokenizer(br.readLine());
            String now = st.nextToken();
            if(now.charAt(0) == '-') break;
            Stack<Character> stack = new Stack<>();
            int cnt = 0;
            for(int i=0;i<now.length();i++){
                char nowC = now.charAt(i);
                if(nowC == '}'){
                    if(stack.isEmpty()){
                        cnt++;
                        stack.add('{');
                    }
                    else if(stack.peek() == '{') stack.pop();

                }
                else if(nowC == '{'){
                    stack.add(nowC);
                }
            }
            if(!stack.isEmpty()){
                cnt += stack.size() / 2;
            }
            System.out.println(turn+". "+cnt);
            turn++;
        }
    }
}

결과

정리

• 예외 케이스가 있을 수 있다고 생각했는데 한번에 됨
• 확실히 특정 규칙으로 만드는 것보다는 카운트만 하면 되서 쉽게 접근