[ 백준 ] 2504 괄호의 값

📌 Problem

소괄호와 대괄호로 이루어진 문자열이 주어진다. 소괄호와 대괄호는 다음과 같이 변환이 가능하다.

() = 2
[] = 3
(P) = P x 2
[P] = P x 3

예를 들어서 (()[[]]) = 2 x (2 + 3 x 3) = 22 으로 변환이 가능하다.
또한 괄호 문자열은 순서쌍이 맞아야 한다. 순서쌍이 맞지 않으면 0을 출력하고 순서쌍이 맞으면 계산된 정수를 출력하면 된다.

📌 Solution

올바른 순서쌍
우선 올바른 괄호 순서쌍인지는 Stack을 사용한다. 여는 괄호는 Stack에 push하며 닫는 괄호는 Stack의 top에 있는 괄호와 비교한다. 만약 Stack이 비어 있거나 쌍이 맞지 않으면 ("()" or "[]") 0을 출력한다.

정수 변환
변수 하나를 1로 초기화하고 괄호들을 차례대로 탐색한다. 여는 괄호가 나왔을 때 소괄호는 2를 대괄호는 3을 곱한다. 닫는 괄호가 나왔을 때는 변수값을 결과값에 더하고 소괄호일 때는 2를 대괄호일 때는 3을 나눈다. 다만, 닫는 괄호가 나올 때마다 더하면 안된다. 예를 들어 (())가 있으면 다음과 같이 연산이 된다.

결과값 = 0, 변수값 = 1
( -> 결과값 = 0, 변수값 = 2
(( -> 결과값 = 0, 변수값 = 4
(() -> 결과값 = 4, 변수값 = 2
() -> 결과값 = 6, 변수값 = 1

계산 과정을 보면 실제 정답인 4와 달리 2를 한 번더 더한 것을 알 수 있다. 그렇기 때문에 여는 괄호가 나오면 flag를 표시하고 닫는 괄호가 나오면 다른 것은 동일하게 동작하되 flag가 있을 때에만 결과값에 더한다.

결과값 = 0, 변수값 = 1, flag = false
( -> 결과값 = 0, 변수값 = 2, flag = true
(( -> 결과값 = 0, 변수값 = 4, flag = true
(() -> 결과값 = 4, 변수값 = 2, flag = false
() -> 결과값 = 4, 변수값 = 1, flag = false

📌 Code

// Data
boolean summed = true;                      // Flag
int sum = 0, mul = 1;                       // sum = result, mul = variable
Stack<Character> stack = new Stack<>();     // Stack for checking available sequence

for (char parenthesis : reader.readLine().toCharArray()) {
    if (parenthesis == '(' || parenthesis == '[') { // Opening
        summed = false;
        stack.push(parenthesis);
        mul *= parenthesis == '(' ? 2 : 3;
    } else { // Closing
        if (stack.isEmpty() ||
                parenthesis == ')' && stack.peek() != '(' ||
                parenthesis == ']' && stack.peek() != '['
        ) {
            sum = 0;
            break;
        }
        if (!summed) {
            sum += mul;
            summed = true;
        }
        mul /= parenthesis == ')' ? 2 : 3;
        stack.pop();
    }
}

result.append(stack.isEmpty() ? sum : 0);