4889 - 안정적인 문자열 (Java)

 

---

 

문제

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

 

 

풀이

단순히 스택을 사용하여 풀 수 있는 문제이다.

 

유명한 괄호 문제랑 거의 똑같은 문제긴 하다.

 

여는 괄호가 나오면 무조건 스택에 넣어준다.

 

그리고 빈 경우에 닫는 괄호라면, 여는 괄호로 바꿔줘서 넣어준다.

스택에 } 이런 값이 하나 있어봤자 이 값은 여는 괄호일때만 사용할 수 있다. 

그렇기 때문에 바꿔준 상태로 넣어준다.

 

그 외에 비지 않았는데 닫는 괄호라면, 스택에는 무조건 여는 괄호가 있기 때문에 짝이 맞는다.

그렇기 때문에 여는 괄호를 빼주면 된다.

 

이 과정을 다 수행후에도 스택에 값이 남아있다면 이는 모두 여는 괄호일것이다.

 

수는 무조건 짝수로, 짝이 맞을거니까 {{{{ 이런 경우나 {{ 이런 경우가 있을것이다.

하나만 닫는 괄호로 바꿔준다음, 2번의 pop 으로 스택에 값을 두개 빼주면 된다.

 

코드

import java.util.*;
import java.io.*;

public class Main {

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Integer printCount = 1;
        while (true) {
            Long operationCount = 0L;
            Stack<String> stack = new Stack<>();
            String inputString = br.readLine();

            if(inputString.indexOf('-') != -1) break;

            String[] strings = inputString.split("");

            for (String token : strings) {
                // stack 이 빈 경우나, 여는 괄호라면
                if(stack.isEmpty() || token.equals("{")){
                    if(token.equals("}")){
                        operationCount++;
                    }

                    stack.push("{");
                    continue;
                }

                // 닫는 괄호라면 -> 빼준다.
                stack.pop();
            }

            while (!stack.empty()) {
                operationCount++;
                stack.pop();
                stack.pop();
            }

            System.out.println(printCount + ". " + operationCount);
            printCount++;
        }

    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

}

 

후기

 

- 실버 1 이라기엔 너무 무난한 문제 아니였나싶다