Baekjoon #2504 괄호의 값

괄호의 값

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

2504번: 괄호의 값

 

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.  만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.  X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.  ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다. 예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다. 여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

 

출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

---

문제를 처음 보았을 때는 아 스택사용해서 계산만 하면 쉽겠네~ 라고 생각했었다.

 

그러나 결코 만만치 않았다.

 

1. 처음 생각은 중첩되는 괄호(ex - [[[]]], ([]) )를 생각하여 재귀함수로 작성하려고 했었다.

-> 계산 값을 주고 받는 과정을 +, * 2가지로 나누어서 생각해야 했는데 이 과정 수행방법을 생각하지 못했다.

(다른 블로그 글들을 보니 재귀함수로 푼 분들도 꽤 있는 것 같지만, 시간 초과가 대부분이어서 반복문으로 해결했다는 글을 많이 보았다.)

 

2. 닫는 괄호를 기준으로 계산하려고 했었다.

여는 괄호가 오면 stack에 push를 수행한다.

닫는 괄호가 나온다면 먼저 짝이 맞는지 확인 후, pop을 수행, 그리고 주어진 값에 맞춰서 tmp *= 2(or 3)을 수행한다. 이 때 만약 다음 괄호가 Open( '(' or '[' )이라면 tmp 값을 value에 더한고 tmp 값을 다시 1로 초기화시켜준다.

마지막으로 stack이 empty가 될 경우 value 값에 마지막으로 들어온 닫는 괄호의 값을 곱하면 그 값(total)이 정답이 된다.

 

(정답이 아니기 때문에 접는 블럭으로...)

 

... 라고 생각했었지만, stack이 empty가 되지 않아도 최종적으로 곱해주어야 하는 경우의 반례가 있었다.

ex) (()[])) : 괄호안에 바로 괄호가 바깥쪽에 중첩해서 있을 경우...

 

stack이 empty가 되는 조건 부분만 바꾸면 해결되는 문제였지만 전-혀 해답을 찾지 못했다. ㅠㅠ

 

3. 위 방법대로 안되서 괄호 계산 식을 다시 써보았더니, 최종적으로 덧셈만 수행하면 되는 식을 찾았다.

풀이 식을 계산 하고 + 만 남기면 닫는 괄호 부분만 남는다. 즉, 둘러싸고 있는 괄호는 이부분에 먼저 곱하면 된다.

 

---

풀이

1. Open 이면 stack.push, tmp *= 2or3

 

2. Close 이면 먼저 stack에 pop할 수 있는지 확인 (-> 없다면 잘못된 문자열)

 

2-1. 문자가 Close1 일 때

2-1-1. 먼저 stack.peek의 값이 Open1인지 확인(-> 아니라면 잘못된 문자열)

2-1-2. 바로 전의 문자가 Open1 문자였다면 중간 값(part)에 tmp 값을 더해준다.

2-1-3. 이 부분은  계산했다는 의미로 tmp를 해당 값(2)으로 나누어준다.

2-1-4. stack.pop

 

2-2. 문자가 Close2 일 때

2-2-1. 먼저 stack.peek의 값이 Open2 인지 확인 (-> 아니라면 잘못된 문자열)

2-2-2. 바로 전의 문자가 Open2 문자였다면 중간 값(part)에 tmp 값을 더해준다.

2-2-3. 이 부분은 계산했다는 의미로 tmp를 해당 값(3)으로 나누어준다.

2-2-4. stack.pop

 

3. 문제가 최종적으로 2개 이상일 수도 있으므로 stack이 한번 empty가 되었다면 최종 정답에 중간 값(part)를 더해준다.

---

전체 코드

/*
* 괄호의 값
* https://www.acmicpc.net/problem/2504
* */

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

public class P2504 {
    static Stack<Character> stack = new Stack<>();

    static final char Open1 = '('; // 40
    static final char Open2 = '['; // 91
    static final char Close1 = ')'; // 41
    static final char Close2 = ']'; // 93

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();

        int total = 0;
        int part = 0;
        int tmp = 1;

        for (int i=0; i<input.length(); i++) {
            char c = input.charAt(i);

            if (c == Open1 || c == Open2) {
                stack.push(c);
                tmp *= c==Open1 ? 2 : 3;
            }
            else {
                if (stack.empty()) {
                    System.out.println(0);
                    return;
                }

                if (c == Close1) {
                    if (stack.peek() != Open1) {
                        System.out.println(0);
                        return;
                    }

                    if (input.charAt(i-1) == Open1) {
                        part += tmp;
                    }
                    tmp /= 2;
                }
                else if (c == Close2) {
                    if (stack.peek() != Open2) {
                        System.out.println(0);
                        return;
                    }
                    if (input.charAt(i-1) == Open2) {
                        part += tmp;
                    }
                    tmp /= 3;
                }
                stack.pop();
            }

            if (stack.empty()) {
                total += part;
                part = 0;
                tmp = 1;
            }
        }

        System.out.println(stack.empty() ? total : 0);

        br.close();
    }
}