[백준 2504] 괄호의 값 / 자바 / 구현(괄호)

#문제         

레벨: G5
알고리즘: 구현(괄호)
풀이시간: 1시간
힌트 참조 유무: 유

https://www.acmicpc.net/problem/2504

---

#문제 풀이        

 

괄호문제가 보면 스택문제임을 깨달아야 한다. 근데 평상시 만났던 괄호가 올바른지 검사하는 문제가 아니라 괄호의 값을 계산하는 문제이다. 바로 문제 설명하겠다.

( ()  () )    <----  이건 2x(2+2)  = 8 이지 않은가 

가장 안쪽에 있느 ()는 원래 2이다. 그런데 우린 () 앞에 (가 있었으므로 4라고 칠 거다.  그 옆에 있는 ()도 4라고 치자. 그럼 답이 8이 나오지 않은가?

이게 어떻게 이렇게 될 수 있을까? 분배법칙 때문에 그렇다. ( ()  () )  는 (()) (()) 와 같다. 즉,  2x(2+2)  이나 (2x2 + 2x2)는 같다. 그러니 우리는 ' ) '를 만나기 전 ' ( '이것들을 임시값 x2로 생각한다. )를 만났는데 배열에서 바로직전이 '(' 이라면, 임시값을 답에 더해주고 임시값은 2로 나눠준다. 왜냐하면 )를 만나서 (를 스택에서 빼줄테니 나누기 2를 해주는 것이 맞다. )를 만났는데 배열 바로 직전이 (가 아니라면 그냥 스택에서 (를 빼주고 2로 나눠준다.  

( ()  () )  로 예시들어보겠다. && temp = 1 로 시작

(                         <---- temp: 1*2 = 2  그리고 스택에 넣음                                         stack: (
( (                       <---- temp 2*2 = 4 그리고 스택에 넣음                                           stack: ( (
( ( )                    <------ ans += 4  그리고 스택에 '('를 뺌 그리고 temp: 4/2 =2         stack: (
( ( )  (                 <------- temp 2*2 = 4 그리고 스택에 넣음                                        stack: ( (
( ( )  ()              <------ ans += 4  그리고 스택에 '('를 뺌 그리고 temp: 4/2 =2             stack: (
( ( )  ()  )            <------ 스택에 '('를 뺌 그리고 temp: 2/2 =1                                       stack: 

 최종 ans : 8

---

#풀이 코드      

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] arr = br.readLine().toCharArray();
        int ans=0;
        int tmp=1;
        Stack<Character> stack = new Stack<>();
        // (x+y)z = zx+zy
        for(int i=0;i<arr.length;i++){
            if(arr[i]=='('){
                stack.add(arr[i]);
                tmp *= 2;
            } else if(arr[i]=='['){
                stack.add(arr[i]);
                tmp *= 3;
            }else if(arr[i]==')'){
                if(stack.isEmpty() || stack.peek()!='('){
                    ans=0;
                    break;
                }
                if(arr[i-1]=='('){
                    ans+=tmp;
                }
                stack.pop();
                tmp/=2;
            }else if(arr[i]==']'){
                if(stack.isEmpty() || stack.peek()!='['){
                    ans=0;
                    break;
                }
                if(arr[i-1]=='['){
                    ans+=tmp;
                }
                stack.pop();
                tmp/=3;
            }
        }
        if(!stack.isEmpty()){
            ans=0;
        }
        System.out.println(ans);
    }
}