4889번 : 안정적인 문자열

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

4889번: 안정적인 문자열

 

문제

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

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

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

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

 

입력

입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우는 없고, 항상 길이는 짝수이다.

입력의 마지막 줄은 '-'가 한 개 이상 주어진다.

 

출력

각 테스트 케이스에 대해서, 테스트 케이스 번호와 입력으로 주어진 문자열을 안정적으로 바꾸는데 필요한 최소 연산의 수를 출력한다.

 

---

소스코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        String arr[];
        Stack<String> stack = new Stack<>();
        String pre = null;
        int result;
        int idx = 1;

        while (true) {
            arr = br.readLine().split("");
            result = 0;
            for(int i=0;i<arr.length;i++) {
                String now = arr[i];
                if(now.equals("-")) break;
                // 스택의 최상단이 "{" 이고 현재 문자열이 "}"일 때
                if(!stack.isEmpty() && stack.peek().equals("{") && now.equals("}")) {
                    stack.pop();
                } else stack.push(now);
            }

            if(arr[0].equals("-")) break; // 종료

            while (!stack.isEmpty()) {
                String now = stack.pop();
                // "{", "{" 또는 "}". "}" 일 때
                if(pre != null && pre.equals(now)) {
                    result += 1; // 연산 1회
                    pre = null;
                }
                // "}", "{" 일 때
                else if(pre != null && !pre.equals(now)) {
                    result += 2; // 연산 2회
                    pre = null;
                } else if(pre == null) pre = now;
            }
            sb.append(idx + ". " + result + "\n");
            idx++;
        }
        System.out.println(sb);
    }
}

 

해결방법

스택을 사용하여 괄호를 처리하는 문제이다. 다음과 같이 접근할 수 있다.

1. 스택에 괄호를 추가한다. 스택의 최상위 괄호와 현재 추가하려는 괄호가 쌍을 이루면 pop()을 수행하고, 그렇지 않으면 push()를 수행하여 유효하지 않은 괄호만 스택에 남도록 한다.
2. 스택에 남아있는 모든 값을 처리한다. 이때, 두 가지 경우로 나뉜다
   • 스택 값이 "{", "{" 일 때: 정상적인 괄호를 위한 연산을 1번 수행한다.
   • 스택 값이 "}", "{" 일 때: 정상적인 괄호를 위한 연산을 2번 수행한다.