백준 2504번 괄호의 값 [Stack] :: 마이구미

이번 글은 백준 알고리즘 문제 2504번 "괄호의 값"을 다뤄본다.

정올 2008년 초등부, 중등부 문제로써, 스택을 응용한 문제가 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자.  ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로  ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고  ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

편의를 위해 여는 괄호 "(" ,"[" 와 닫는 괄호 ")", "]" 라고 표현하겠다.

(()) 이 괄호는 바깥 괄호에 둘러싸여있기 때문에, 2 * 2 가 된다.

(()()) 이 괄호의 내부 2개의 괄호는 바깥 괄호에 둘러싸여 있지만, 서로 다른 괄호이다.

그렇기에, 2 * (2 + 2)가 된다.

이 부분을 잘 기억하고 이해해야 문제를 풀 수 있다.

문제의 접근 방식은 아래와 같다. (올바른 괄호열이라고 가정하자)

1. 여는 괄호는 스택에 푸시한다. "(", "["
2. 닫는 괄호는 스택의 top을 팝한 후, 계산 된 정수를 푸시한다. ")", "]"
3. 최종 스택에는 정수들만 남게 됨으로써, 모든 값을 더해준다.

사칙연산의 계산을 스택으로 활용하는 것과 비슷한 흐름이라고 생각하면 된다.

그림으로 표현하면 아래와 같다.

 코드로 자세한 설명을 계속해보겠다.

if (array[i].equals("(") || array[i].equals("[")) {
    stack.push(array[i]);
} else {
    if (array[i].equals(")")) {
        if (stack.peek().equals("(")) {
            // 한쌍을 이루는 괄호일 때
            stack.pop();
            stack.push("2");
        } else {
            check = stackInnerLoop(stack, "[", "(", 2);
        }
    } else { // "]"
        if (stack.peek().equals("[")) {
            stack.pop();
            stack.push("3");
        } else {
            check = stackInnerLoop(stack, "(", "[", 3);
        }
    }
}

루프를 돌면서, 닫는 괄호 시, 이전 괄호가 한쌍에 맞는 여는 괄호라면, top을 pop한 후, 2 또는 3을 push한다.

하지만, 닫는 괄호이지만, 한쌍에 맞지 않는 경우가 존재한다. (위 그림 표현 참고)

이 경우에는, 스택을 pop 하면서 2가지로 행위를 하면 된다.

스택의 top이 정수일 경우에는 서로 다른 괄호이기 때문에 더하면 된다.

그렇지 않은 경우는, 한쌍을 이루기 때문에 곱한 후, 다시 스택에 push 해주면 된다.

// () 한쌍을 이룰 경우 s1 - "[", s2 - "(", value - 2
// [] 한쌍을 이룰 경우 s1 - "(", s2 - "[", value - 3
public static int stackInnerLoop(Stack<String> stack, String s1, String s2, int value) {
    int result = 0;

    while (!stack.isEmpty()) {
        String top = stack.peek();

        if (top.equals(s1)) {
            return -1;
        } else if (top.equals(s2)) {
            stack.pop();
            result *= value;
            stack.push(String.valueOf(result));
            break;
        } else {
            result += Integer.parseInt(stack.pop());
        }
    }

    return result;
}

이 과정이 끝나면, 최종 스택에는 올바른 입력이 주어졌을 경우, 아래와 같은 정수들을 가지고 있다.

()()()() 입력일 경우, 2, 2, 2, 2

([])()[] 입력일 경우, 6, 2, 3

((()))() 입력일 경우, 8, 2

즉, 스택에 정수가 아닌 값이 들어있다면, 올바르지 않은 괄호열이 주어진 경우가 된다.

예외에 대한 처리는 아래 Github URL을 통해 전체 코드를 확인하길 바란다.

기본적인 스택 문제보다 난이도는 높지만, 매우 높지는 않다.

기본적은 스택 문제를 풀었다면, 스택의 응용을 위한 좋은 문제가 된다.

이 문제는 올바르지 않은 괄호에 대한 반례가 많이 존재하여 오답률이 높은 문제라 생각한다.

본인의 생각으로는, 문제는 반례를 생각하는 것을 원하는 것 같다.

백준 알고리즘 2504번 "괄호의 값" 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/2504.java