백준 2504 괄호의 값 (JAVA 자바 풀이)

백준 2504 괄호의 값 (JAVA 자바 풀이)

 

---

 

 

문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 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 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.

입력

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

출력

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

 

 

---

 

 

💡 풀이 과정

 

 

스택을 사용해서 풀 수 있는 문제이다. 

이전 괄호 문제에서는 괄호열을 판단하는 수준이었는데 이 문제는 계산까지 해주어야 해서 난이도가 높다고 느껴졌다. 주어진 문자열을 한 글자씩 읽으면서 스택을 사용해 이 두 가지를 동시에 처리해야 한다. 

 

풀이 방법은 여러 가지가 있는 것 같다. 일반적인 풀이의 핵심은 문제에서 제시한 그대로 괄호 안의 값을 최대한 먼저 계산해서 (X) 형태로 만들어 주어야 한다는 점이다. 

 

중첩 괄호의 depth를 잘 관리해주어야 우선순위에 맞게 계산할 수 있는 문제이다. 

 

그렇다면 depth를 어떻게 관리하느냐가 핵심이다. 클래스를 만들어서 괄호의 종류와 value를 관리하는 방법도 있는데 이번 풀이에서는 별도의 스택을 통해 풀이하도록 했다. 

 

두 개의 스택을 사용하는데, 하나는 괄호 자체를 저장하기 위한 것이고, 다른 하나는 괄호의 값을 저장하기 위한 것이다. 다음과 같이 초기화한다. 

 

Deque<Character> stack = new LinkedList<>();
Deque<Integer> valueStack = new LinkedList<>();

이제, 주어진 괄호들에 대해서 반복문을 돌면서, 여는 괄호가 나타나면 해당 괄호를 괄호 스택에 푸시하고, 값 스택에는 0을 푸시한다. 이는 아직 괄호 쌍이 완성되지 않았음을 의미할 때이다. 

 

for (char ch : bracketString.toCharArray()) {
   if (ch == '(' || ch == '[') {
      stack.push(ch);
      valueStack.push(0); // 임시 값으로 0을 삽입

 

 

닫는 괄호가 나타날 때를 생각해 보자. 이 때에는 해당 괄호가 우선 이전의 것과 맞는 종류인지를 검사해주어야 한다. 괄호 스택에서 최근에 푸시된 괄호를 확인하여 짝이 맞는지 검사한다.

 

if (isNotMatch(stack, '(')) {
   return 0; // 올바르지 않은 괄호
}

 

짝이 맞다면 해당 괄호 쌍에 대한 값을 계산하여 값 스택에 저장해야 한다. 또한 일단 맞다면 괄호 스택의 맨 위에 있는 괄호는 빼주어서 다음으로 진행할 수 있게 해준다.

 

stack.pop();

 

그런 뒤, '()'의 경우 값 스택에 2를 저장하고, '[]'의 경우에는 3을 저장한다. 이때 중첩을 고려해서 값을 계산해주는 로직이 필요하다.

중첩된 괄호의 경우, 예를 들어 '(X)' 또는 '[X]'와 같은 경우, X의 값이 먼저 계산되어 값 스택에 저장되어 있을 것이다. 그렇게 되도록 로직을 만들어 주어야 한다. 이때는 X의 값을 꺼내어 '()' 또는 '[]'에 해당하는 값을 곱해준다. 만약 그렇지 않다면 같은 depth라는 것을 의미한다. 따라서 이 경우에는 값을 더해준다. 

 

int value = valueStack.pop();
int newValue = value == 0 ? 2 : value * 2; // 괄호값 계산

 

먼저 0인 케이스와 이때 해당 숫자를 그대로 다시 넣어주는 경우를 생각해보자. 어째서 그럴까? 맨 처음 valueStack을 초기화할 때 0을 넣어주기로 했다. 그렇기 때문에 기본 값인 경우 0인 것이다. 

 

그렇다면 곱해야 할때는 언제일까? 

 

addToPrevious(valueStack, newValue);

 

private static void addToPrevious(Deque<Integer> valueStack, int newValue) {
   if (!valueStack.isEmpty()) {
      int previousValue = valueStack.pop();
      valueStack.push(previousValue + newValue);
   } else {
      valueStack.push(newValue);
   }
}

 

 

바로 위의 이어지는 케이스에서, 즉 match 하는 괄호가 나왔을 때이다. 따라서 match 하는 경우가 나온 경우 그 값을 넣어줌으로써 다음 값이 match인 경우라면 곱하기가 되도록 해준다. 

여기서의 과정이 서로 다른 올바른 괄호열이 연결되어 있는 경우, 예를 들어 'XY'와 같은 경우, 각각의 괄호열 X와 Y의 값을 더해 최종 괄호값을 계산하도록 하는 것이다.

 

조금 더 이해를 쉽게 하기 위해서 예시를 들어 생각해 보자. 

 

기본적인 괄호 쌍 -> '()' 또는 '[]'

이 경우 가장 간단하다. 예를 들어, 단순히 '()'가 입력된 경우, 이 괄호 쌍의 값은 2이다. 이 때는 값 스택에 0을 넣어두었다가, 닫는 괄호가 나타나면 0 대신 2를 스택에 넣는 것이다.

 

연속된 괄호열 -> 'XY'

여기서 X와 Y는 서로 다른 올바른 괄호열이다. 예를 들어, '()[]'의 경우, '()'는 2의 값을, '[]'는 3의 값을 가지는데, 이들이 연속되어 있으므로, 이들의 합인 5(2+3)가 된다.

 

여기서 더하기 로직을 생각해 보면, 연속된 괄호열에서는 각 괄호열의 값이 단순히 더해져야 한다. 이것이 `addToPrevious` 함수에서 처리되는 로직으로, 값 스택에서 이전 값과 현재 값을 더해 다시 스택에 넣음으로써 연속된 괄호열의 값을 계산하는 과정이다. 

1. 스택에서 이전 값(여기서는 '()'의 값인 2)을 꺼낸다.
2. 새로 계산된 값(여기서는 '[]'의 값인 3)을 이전 값과 더한다.
3. 계산된 총합(5)을 스택에 다시 넣는다.

 

중첩된 괄호 -> '(X)' 또는 '[X]'

여기서 X는 이미 계산된 괄호열의 값이다. 예를 들어, '(()())'를 보면, 내부의 '()'는 각각 2의 값을 가지므로, 외부의 '()' 안에 있는 총합은 4(2+2)가 된다. 이 경우 외부의 괄호로 감싸진 총합에 2를 곱하여 8이 되어야 한다.

 

여기서 곱하기 로직을 생각해 보면, 닫는 괄호가 나타났을 때, 그에 해당하는 여는 괄호까지의 괄호열은 중첩된 괄호로 간주된다. 이때 스택의 최상단 값이 0이 아니라면, 이미 계산된 내부 괄호열의 값이 있는 것으로, 이 값을 괄호의 종류에 따라 2를 곱한다.  

 

1. 스택에서 이전 값(내부 '()'의 합인 4)을 꺼낸다.
2. 새로 계산된 값(외부 '()'의 값인 2)을 이전 값과 곱합니다. 여기서는 4 * 2 = 8이 된다.
3. 계산된 곱셈 결과(8)를 스택에 다시 넣는다.

 

 

다시 한 번 코드로 보면 다음과 같다. 

 

} else if (ch == ')') {
   if (isNotMatch(stack, '(')) {
      return 0; // 올바르지 않은 괄호
   }
   stack.pop();
   int value = valueStack.pop();
   int newValue = value == 0 ? 2 : value * 2; // 괄호값 계산
   addToPrevious(valueStack, newValue);

private static void addToPrevious(Deque<Integer> valueStack, int newValue) {
   if (!valueStack.isEmpty()) {
      int previousValue = valueStack.pop();
      valueStack.push(previousValue + newValue);
   } else {
      valueStack.push(newValue);
   }
}

 

 

마지막으로 스택에 더 이상 들어올 게 없는데도 괄호가 남아 있으면 비정상 이므로 0을 리턴한다. 

 

if (!stack.isEmpty())
   return 0; // 남아있는 괄호가 있다면 올바르지 않은 괄호열

 

 

최종 값은 남아 있는 값들을 더하면 되므로 

return valueStack.stream().mapToInt(Integer::intValue).sum(); // 최종 값 계산

 

 

예시로 주어진 괄호열의 스택 프로세스를 그림으로 그려보면 다음과 같다. 

 

 

 

 

 

 

💡 코드 구현

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {

   private static StringTokenizer receiveInput(BufferedReader bufferedReader) throws IOException {
      return new StringTokenizer(bufferedReader.readLine());
   }

   public static void main(String[] args) throws IOException {

      // BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
      BufferedReader bufferedReader = new BufferedReader(new FileReader("input.txt"));

      StringTokenizer stringTokenizer = receiveInput(bufferedReader);

      System.out.println(calculateBracketValue(stringTokenizer.nextToken()));
   }

   private static int calculateBracketValue(String bracketString) {
      Deque<Character> stack = new LinkedList<>();
      Deque<Integer> valueStack = new LinkedList<>();

      for (char ch : bracketString.toCharArray()) {
         if (ch == '(' || ch == '[') {
            stack.push(ch);
            valueStack.push(0); // 임시 값으로 0을 삽입
         } else if (ch == ')') {
            if (stack.isEmpty() || stack.peek() != '(')
               return 0; // 올바르지 않은 괄호열
            stack.pop();
            int value = valueStack.pop();
            int newValue = value == 0 ? 2 : value * 2; // 괄호값 계산
            addToPrevious(valueStack, newValue);
         } else if (ch == ']') {
            if (stack.isEmpty() || stack.peek() != '[')
               return 0; // 올바르지 않은 괄호열
            stack.pop();
            int value = valueStack.pop();
            int newValue = value == 0 ? 3 : value * 3; // 괄호값 계산
            addToPrevious(valueStack, newValue);
         }
      }

      if (!stack.isEmpty())
         return 0; // 남아있는 괄호가 있다면 올바르지 않은 괄호열

      return valueStack.stream().mapToInt(Integer::intValue).sum(); // 최종 값 계산
   }

   private static void addToPrevious(Deque<Integer> valueStack, int newValue) {
      if (!valueStack.isEmpty()) {
         int previousValue = valueStack.pop();
         valueStack.push(previousValue + newValue);
      } else {
         valueStack.push(newValue);
      }
   }

}