2022.03.04 69일차

백준 4889번 (안정적인 문자열)

문제

여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다.

1. 빈 문자열은 안정적이다.
2. S가 안정적이라면, {S}도 안정적인 문자열이다.
3. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다.

{}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다.

문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다.

나의 풀이

1. {, }의 경우의 수 생각하기, '-'이 나오면 중단하기 => stack으로 접근
2. stack이 비어있을 때 }인 경우 무조건 변경 필요(count 1증가), {로 추가하기
3. stack이 {로 채워져있는 상태에서 {가 오면 stack에 그대로 추가
4. stack이 {로 채워져있는 상태에서 }가 오면 stack.pop 실행
5. 남아있는 stack 길이로 stack.size() / 2를 하면 변경해야 하는 횟수(기존 count와 더하기)
6. stack.contains("-")를 활용해 -가 나오면 반복문 중단

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));
        String temp = br.readLine();
        int number = 1;

        while (test(temp)) {
            Stack<String> stack1 = new Stack<>();
            int count = 0;

            for (int i = 0; i < temp.length(); i++) {
                if (stack1.isEmpty() && temp.charAt(i) == '}') {
                    count++;
                    stack1.push("{");
                } else if (stack1.contains("{") && temp.charAt(i) == '}') {
                    stack1.pop();
                } else {
                    stack1.push("{");
                }
            }

            count += stack1.size() / 2;

            System.out.println(number + ". " + count);
            number++;
            temp = br.readLine();
        }
    }

    static boolean test (String input) {
        return !input.contains("-");
    }
}

생각하기