[BOJ] 백준 4889 - 안정적인 문자열 풀이

1. 문제

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

4889번: 안정적인 문자열

 

2. 풀이

백준 실버 1 문자열에 해당하는 문제이다.
백준 문제에서 괄호를 몇 번 풀어봐서 그런지 보자마자 스택을 이용하여 풀어야 한다는 것을 알았다. (물론 금방 풀지는 못했지만...)

문제의 핵심은 입력으로 주어지는 문자열을 안정적인 문자열로 바꾸기 위한 최소한의 연산 횟수이다.
우선 Character로 스택을 만들어준다.(9번 줄)
입력의 횟수가 주어지지 않고 '-'가 마지막 줄에 주어진다고 했으므로 "-"가 포함된 입력이 주어질 시 while을 빠져나오도록 만들었다.(16번 줄)
입력을 받으면 반복문으로 각 자리의 문자를 탐색하고, 탐색한 문자는 switch문에 맞게 로직을 수행한다.

1. 열린 괄호의 경우 ( '{' )
- 열린 괄호의 경우 안정적인 문자열이 되기 위한 첫 번째 조건이므로 스택에 push해준다.(24번 줄)

2. 닫힌 괄호의 경우 ( '}' )
- 닫힌 괄호의 경우는 2가지로 분류된다.

(1) 스택이 비어있을 경우
- 스택이 비어있으므로 안정적인 문자열을 만들기 위해서는 열린 괄호가 들어가야 한다. 따라서 연산 횟수(result)를 하나 늘리고 열린 괄호를 스택에 넣어준다.(29, 30번 줄)

(2) 마지막에 스택에 집어넣은 문자가 열린 괄호의 경우 
- 스택의 마지막 문자가 열린 괄호라면 현재 탐색하는 문자가 닫힌 괄호이므로 이를 합치면 안정된 문자가 된다. 따라서 닫힌 괄호를 스택에 넣지 않고 열린 괄호를 스택에서 빼준다. (32번 줄)

문자를 다 탐색했다면 이제 스택에 남아있는 문자열을 확인해야 한다.
스택이 빌 때까지 스택에서 하나씩 꺼내어 마지막에 꺼낸 문자(oldBracket)와 비교한다.
앞선 while 반복문에서 닫힌 괄호는 스택에 넣어주지 않았기 때문에 열린 괄호와 전에 꺼냈던 문자와 비교하여 result를 카운트하게 된다.

그 후 결과를 출력하면 정답!!

 

3. 소스 코드

import java.io.*;
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));

        Stack<Character> stack = new Stack<>();
        int order = 1;
        
        while (true) {
            int result = 0;
            String input = br.readLine();

            if (input.contains("-")) {
                break;
            }

            for (int i = 0; i < input.length(); i++) {
                char c = input.charAt(i);
                switch (c) {
                    case '{':
                        stack.add(c);
                        break;

                    case '}':
                        if (stack.isEmpty()) {
                            result += 1;
                            stack.add('{');
                        } else if (stack.peek() == '{') {
                            stack.pop();
                        }
                        break;
                }
            }

            char oldBracket = ' ';
            while (!stack.isEmpty()) {
                char c = stack.pop();
                switch (c) {
                    case '{':
                        if (oldBracket == '{') {
                            result += 1;
                            oldBracket = ' ';
                        } else {
                            oldBracket = '{';
                        }
                        break;
                }
            }

            bw.write(Integer.toString(order) + ". " + Integer.toString(result) + "\n");
            order++;
        }

        bw.flush();
        bw.close();
        br.close();
    }
}