[백준] 4889 안정적인 문자열 - Data Structure / Java

• 문제 링크

4889번: 안정적인 문자열

 

• 풀이 과정

입력받은  문자열의 각각의 괄호를 확인하여 여는 괄호라면 stack에 push하고,

닫는 괄호이고, stack이 비어있을 경우 해당 괄호를 뒤집는 연산을 수행하는 의미로 여는 괄호를 push 및 cnt++ 수행,

stack이 비어있지 않다면 안정적인 문자열을 만들 수 있으므로 stack을 pop한다.

 

위와 같은 과정을 수행 후 스택은 비어있거나 여는 괄호만 존재하게된다.

따라서 입력은 짝수개의 괄호이므로 스택에 존재하는 괄호의 절반을 닫는 괄호로 변경하며,

현재 연산의 수 + stack의 크기의 절반이 한 테스트 케이스 당 연산의 횟수가 된다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();
        int tc = 1;

        String input;
        while ((input = br.readLine()).charAt(0) != '-') {
            Stack<Character> stk = new Stack<>();
            int cnt = 0;

            for (int i = 0; i < input.length(); i++) {
                char token = input.charAt(i);
                if (token == '{')
                    stk.push(token);
                else if (stk.isEmpty()) {
                    stk.push('{');
                    cnt++;
                } else
                    stk.pop();
            }

            sb.append(tc++).append(". ").append(cnt + stk.size() / 2).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
    }

}