[백준 BOJ / JAVA] 괄호의 값 (2504번)

📘 1. 문제 소개

2504번: 괄호의 값

 

📘 2. 풀이

  해당 문제는 일반적인 스택 문제에 값을 구하는 문제가 더해진 문제다. 괄호를 이용한 일반적인 스택 문제에 대한 설명은 아래 문제를 참고하도록 하자.

9012번: 괄호

 

  이제부터 괄호들을 이용한 계산을 통해 어떻게 값을 구하는지 생각해 보자.

  주어진 예제인 ( ( ) [ [ ] ] ) ( [ ] )를 살펴보자. 일반적으로 계산을 한다고 하면, 2 x (2 + (3 x 3)) + (2 x 3) = 28로 계산할 수 있다. 여기서 문제는 언제 더해주고(+) 언제 곱해주어야(x) 하는지를 정확히 나눌 수 없다는 것이다. ('곱하기 안에 더하기'를 만들 수 있고 '더하기 안에 곱하기'를 만들 수 있어서 계산이 복잡하다.)

 

  ( ( ) [ [ ] ] ) ( [ ] )를 다시 한번 살펴보자.

  값을 위와 같이 2 x (2 + (3 x 3)) + (2 x 3) = 28로 표시할 수도 있겠지만, (2 x 2) + (2 x 3 x 3) + (2 x 3) = 28로 표시할 수도 있다. 이렇게 표시하면 더하기(+)와 곱하기(x)가 정확히 분리할 수 있다. 곱하기를 이용한 식 안에 더하기가 없다는 것이다. 그렇기 때문에 곱하기를 이용해서 값이 구해진 상태에서 더하기를 이용하여 값을 더하고 이를 반복하면 된다.

 

  그렇다면 언제 곱하기(x)를 하고 언제 더하기(+)를 해야 할까?

  곱하기는 괄호가 열릴 때 해주고 더하기는 직전 괄호와 짝을 이룰 때 해주면 된다.

예제 : ( ( ) [ [ ] ] ) ( [ ] )

(	(	)	)
x2	x2	+
(	[	[	]	]	)
x2	x3	x3	+
(	[	]	)
x2	x3	+

  이렇게 표현하면 ( ( ) [ [ ] ] ) ( [ ] )를 (2 x 2) + (2 x 3 x 3) + (2 x 3) = 28라고 계산할 수 있다.

 

  이를 간단하게 식으로 표현하면 아래와 같다.

• 전체 값 = totalScore
• 곱하기를 이용한 하나의 값 = score

1. (
   score = score x 2
2. [
   score = score x 3
3. )
   직전 괄호와 짝을 이루는 경우
   → totalScore = totalScore + score
   → score = score / 2
   직전 괄호와 짝을 이루지 못하는 경우
   → score = score / 2
4. ]
   직전 괄호와 짝을 이루는 경우
   → totalScore = totalScore + score
   → score = score / 3
   직전 괄호와 짝을 이루지 못하는 경우
   → score = score / 3

 

📘 3. 코드

public class Main {

    static String s;
    static boolean isValid = true;
    static int totalScore, score = 1;

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

        s = in.readLine();
        Stack<Character> stk = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            switch (c) {
                case '(':
                    score *= 2;
                    stk.add(c);
                    break;

                case '[':
                    score *= 3;
                    stk.add(c);
                    break;

                case ')':
                    if(stk.isEmpty() || stk.peek() != '(') {
                        isValid = false;
                        break;
                    }

                    if(s.charAt(i-1) == '(') {
                        totalScore += score;
                        score /= 2;
                    }
                    else {
                        score /= 2;
                    }

                    stk.pop();
                    break;
                    
                case ']':
                    if(stk.isEmpty() || stk.peek() != '[') {
                        isValid = false;
                        break;
                    }

                    if(s.charAt(i-1) == '[') {
                        totalScore += score;
                        score /= 3;
                    }
                    else {
                        score /= 3;
                    }

                    stk.pop();
                    break;
            }

            if(!isValid)
                break;
        }

        if (isValid && stk.isEmpty()) {
            System.out.println(totalScore);
        }
        else {
            System.out.println(0);
        }
    }
}