백준: 4889 안정적인 문자열 [포포의 알고리즘]

문제

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

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

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

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

입력

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

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

출력

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

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

4889번: 안정적인 문자열

---

내 제출

public class No4889 {
    static int n;
    static int count;
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();
        n = 1;
        while(true){
            String s = br.readLine();
            if(s.contains("-")) {
                System.out.println(sb);
                break;
            }
            count = 0;
            String[] arr = s.split("");
            Stack<String> st = new Stack<>();
            for (int i = 0; i < arr.length; i++) {
                if(arr[i].equals("{")){
                    st.push(arr[i]);
                }
                else if(arr[i].equals("}")){
                    if(st.isEmpty()){
                        count++;
                        arr[i] = "{";
                        st.push(arr[i]);
                    }else{
                        st.pop();
                    }
                }
            }
            if(!st.isEmpty()){
            	count += st.size()/2;
            }
            
            sb.append(n+". "+count).append('\n');
            n++;
        }
    }
 }

1. 스택을 생성한 뒤, 여는 괄호 { 라면 스택에 push 해준다. 입력을 문자열로 받은 뒤 배열로 변환하였는데, 입력받은 문자열을 바로 스택에 저장해도 될 듯..

2. 닫는 괄호를 입력받으면, 1) 스택이 비어있는 경우 2) 스택에 여는 괄호가 있는 경우로 나뉜다.
스택이 비어있는 경우에는, 닫는 괄호를 여는 괄호로 변환하고, 교정한 횟수(count)를 더한다.
만약 스택에 여는 괄호가 있었다면, 그냥 스택에서 pop연산을 취한다.

3. 모든 입력이 끝나고도 스택이 비어있지 않은 경우에는, 입력받는 문자열의 개수가 짝수이므로
스택의 size / 2 를 교정한 횟수(count)에 더해준다.

예를 들어, 마지막입력이  { { { { 로 끝나는 경우, 스택에 그대로 남게 되는데 
정확히 절반만 닫는 괄호로 바꾸면 되기 때문이다.