Baekjoon 2504 괄호의 값 - Stack

더 깔끔한 노션을 원한다면

Baekjoon 2504 괄호의 값 - Stack

2504번: 괄호의 값

설계

1. 괄호의 종류는 '(', ')', '[', ']' 총 4개이다.

2. 각 괄호에 따라 sum을 바꿔준다.

   '(' 일 때에는 sum*=2

   '[' 일 때에는 sum*=3

   ')' 일 때에는 sum/=2

   ']' 일 때에는 sum/=3

3. 마지막 stack이 비어있는지 확인해준다.

1. '('와 '['일 경우

case '(':
  sum *= 2;
  stack.push(ch);
  break;
case '[':
  sum *= 3;
  stack.push(ch);
  break;

'('일 때에는 sum에 2를, '['일 때에는 sum에 3을 곱해준 뒤, stack에 넣어준다.

2. ')'와 ']'일 경우

case ')':
  if (stack.isEmpty() || stack.pop() != '(') {
    return 0;
  }
case ')':
  if (stack.isEmpty() || stack.pop() != '(') {
    return 0;
  }
  if (S.charAt(i - 1) == '(')
    answer += sum;
    sum /= 2;
    break;
case ']':
  if (stack.isEmpty() || stack.pop() != '[') {
    return 0;
  }
  if (S.charAt(i - 1) == '[')
    answer += sum;
  sum /= 3;
  break;    answer += sum;
    sum /= 2;
    break;
case ']':case ')':
  if (stack.isEmpty() || stack.pop() != '(') {
    return 0;
  }
  if (S.charAt(i - 1) == '(')
    answer += sum;
    sum /= 2;
    break;
case ']':
  if (stack.isEmpty() || stack.pop() != '[') {
    return 0;
  }
  if (S.charAt(i - 1) == '[')
    answer += sum;
  sum /= 3;
  break;
  if (stack.isEmpty() || stack.pop() != '[') {
    return 0;
  }
  if (S.charAt(i - 1) == '[')
    answer += sum;
  sum /= 3;
  break;

이 때 주의할 점은 stack이 비어있는지(isEmpty), stack의 pop이 올바른 괄호인지 확인해줘야 한다.

그러고 나서 문자열의 전 문자가 짝이 맞는 괄호라면 answer에 sum을 더해준다.

이러한 수식이 나오는 이유는 다음과 같다.

(()[[]])([])
[1] => 2 * (2 + (3 * 3)) + (2*3)
[2] => (2*2) + (2*3*3) + (2*3)

[1]을 [2]로 풀어서 계산하기 때문에 전 문자가 짝이 맞는지 확인해주는 것이다.

3. 마지막에 stack이 비어있는지 확인

if (!stack.isEmpty()) {
    return 0;
  }if (!stack.isEmpty()) {
    return 0;
  }

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    Baekjoon solution = new Baekjoon();
    System.out.println(solution.P2504());
  }
}

class Baekjoon {
  Stack<Character> stack = new Stack<>();

  public int P2504() throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String S = br.readLine();
    int answer = 0;
    int sum = 1;
    int stringSize = S.length();
    for (int i = 0; i < stringSize; i++) {
      char ch = S.charAt(i);
      switch (ch) {
        case '(':
          sum *= 2;
          stack.push(ch);
          break;
        case '[':
          sum *= 3;
          stack.push(ch);
          break;
        case ')':
          if (stack.isEmpty() || stack.pop() != '(') {
            return 0;
          }
          if (S.charAt(i - 1) == '(')
            answer += sum;
          sum /= 2;
          break;
        case ']':
          if (stack.isEmpty() || stack.pop() != '[') {
            return 0;
          }
          if (S.charAt(i - 1) == '[')
            answer += sum;
          sum /= 3;
          break;
      }
    }
    if (!stack.isEmpty()) {
      return 0;
    }
    return answer;
  }
}