[백준 2504] - [스택] - 괄호의 값 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/2504

---

이문제는 백준 9012 번 문제의 업그레이드 문제이다. 

본인의 풀이와 문제링크를 첨부한다.

---

백준 9012 문제 링크

2018/11/30 - [알고리즘/스택(Stack)] - [백준 9012] - [스택] - 괄호 (JAVA)

---

이전글에서 유효한 괄호 문자열을 만드는거에 괄호갖는 값 을 계산하는 문제이다. 

여는 괄호가 나올때는 문제없이 스택에 PUSH 하면 되지만 닫는 괄호가 나올때가 문제이다. 

[ ( ) ] 의 괄호 문자열이 입력 됐다면 답은 6이 나온다.

왜 그럴까?

() 괄호가 갖는 값은 2 이고 []괄호가 갖는 값은 3

X가 정수일때 (X)는 X*2 이고 [X] 는 X*3이라고 하니깐

[ ( ) ] 는 [2] 로 되고 6이 나오는 것이다.

그럼 문제를 어떻게 풀까?

예제로 제공된 괄호 문자열로 문제를 풀어보자. 

(()[[]])([])

위의 괄호 문자열이 제공 됐다.

여는 괄호가 나오면 본인의 닫는 괄호를 스택에 PUSH 할것이다. 

순서 1 :

괄호 : ' ( '

스택 목록 : [ ]

여는 괄호이니 본인의 닫는 괄호를 스택에 PUSH 한다.

순서 2 : 

괄호 : ' ( '

스택 목록 : [ ')' ]

여는 괄호이니 본인의 닫는 괄호를 스택에 PUSH 한다.

순서 3:

괄호 : ' ) '

스택 목록 : [ ')', ')' ]

닫는 괄호가 나왔고 스택에 본인과 맞는 괄호가 있으므로 POP 한다.

()는 값이 2이므로 2를 스택에 PUSH 한다.

순서 4: 

괄호 : ' [ '

스택 목록 : [ ' ) ', '2' ] 

여는 괄호가 나왔으므로 스택에 PUSH 한다.

순서 5 :

괄호 : ' [ '

스택 목록 : [ ' ) ' , ' 2 ' , ' ] ' ]

여는 괄호가 나왔으므로 스택에 PUSH 한다.

순서 6 :

괄호 : ' ] '

스택 목록 : [ ' ) ' , ' 2 ' ,  ' ] ' ,  ' ] ' ]

닫는 괄호가 나왔고 스택에 본인과 맞는 괄호가 있으므로 POP 한다.

[] 는 값이 3 이므로 3을 스택에 PUSH 한다.

순서 7 :

괄호 : ' ] '

스택 목록 : [ ' ) ' , ' 2 ' , ' ] ', 3 ]

닫는 괄호가 나왔고 스택에 있는 숫자를 POP 하고 나면 본인과 맞는 괄호이므로 괄호 역시 POP 한다.

[X] 은 X * 3이므로 9를 PUSH 한다.

순서 8 : 

괄호 : ' ) '

스택 목록 : [ ' ) ' , ' 2 ' , ' 9 ' ]

닫는 괄호가 나왔고 스택에 있는 모든 수를 POP 하면서 더한다.

모든 수를 POP 하고 나면 괄호가 남았고 본인과 맞는 괄호이므로 괄호 역시 POP 한다.

POP 하면서 나온 모든 수를 더한 값 11 에 ()의 값이 2를 곱한뒤 스택에 PUSH 한다.

순서 9 :

괄호 : ' ( '

스택 목록 : [ 22 ]

여는 괄호가 나왔으므로 스택에 PUSH 한다.

순서 10 : 

괄호 : ' [ '

스택 목록 : [ 22, ' ) ' ]

여는 괄호가 나왔으므로 스택에 PUSH 한다.

순서 11 : 

괄호 : ' ] '

스택 목록 : [ 22, ' ) ' , ' ] ' ]

닫는 괄호가 나왔고 스택에 본인과 맞는 괄호가 있으므로 POP 한다.

[]는 값이 3이므로 3을 스택에 PUSH 한다.

순서 12 : 

괄호 : ' ) '

스택 목록 : [ 22, ' ) ' , 3 ]

닫는 괄호가 나왔고 스택에 있는 숫자를 POP 하고 나면 본인과 맞는 괄호이므로 괄호 역시 POP 한다.

(X) 은 X * 2이므로 6을 PUSH 한다.

위의 과정을 모두 끝내면 스택에는 22와 6 숫자가 남아 있고

이 숫자들을 스택에서 POP 하면서 더해주면 된다.

이 문제를 풀때 주의사항은 아래와 같다.

1) 모든 과정은 끝낸뒤에는 무조건 스택에는 숫자만 남아 있어야 한다.

2) 닫는 괄호일때 스택 TOP이 숫자 일 경우 숫자들은 POP 하면서 전부 더하고 본인의 괄호 계산값을 곱하여 다시 PUSH 한다.

3) 닫는 괄호일때 스택 TOP이 숫자가 아니고 바로 본인 괄호일때 본인 괄호 값만 스택에 PUSH한다.

소스

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        
        Stack<String> stack = new Stack<String>();
        
        boolean isAble = true;
        for(int i=0; i < str.length(); i++) {
            String c = str.substring(i, i+1);
            
            // 여는 괄호일 경우 본인의 닫는 괄호를 스택에 저장한다.
            if("(".equals(c)) {
                stack.push(")");
                continue;
            }
            
            if("[".equals(c)) {
                stack.push("]");
                continue;
            }
            
            // 닫는 괄호일경우 까다롭다.
            // 스택이 빌때까지 계속 꺼낸다.
            // 아직 짝이 안됐는데 스택이 비어있다면 isAble은 false가 된다.
            // 숫자 혹은 본인과 맞는 괄호가 아닌게 나온다면 isAble은 false가 된다.
            // 숫자가 나오면 숫자는 계속 합한다.
            // 본인에 맞는 괄호가 나오면 본인 괄호 크기에 맞게 위에 합한 수를 곱을 한뒤 그 값을 스택에 PUSH 한다.
            int num = 0;
            while(true) {
                // 아직본인 괄호가 나오지 않았는데 스택이 비었다는 뜻 유효하지 않은 괄호 문자열
                if(stack.isEmpty()) {
                    isAble = false;
                    break;
                }
                
                if(isNumber(stack.peek())) {
                    num += Integer.parseInt(stack.pop());
                }else {
                    if(isVPS(c, stack.peek())) {
                        stack.pop();
                        int t = (")".equals(c)) ? 2:3;
                        
                        if(num == 0) {
                            stack.push(String.valueOf(t)); 
                        }else {
                            stack.push(String.valueOf(t*num));
                        }
                        break;
                    }else {
                        isAble = false;
                        break;
                    }
                }
            }
            if(!isAble) break;
        }
        
        int result = 0;
        
        // 스택이 빌때까지 POP한다.
        //정상적인 괄호 문자열이라면 스택에는 숫자만 들어 있어야 한다.
        while(!stack.isEmpty()) {
            if(isNumber(stack.peek())) {
                result += Integer.parseInt(stack.pop());
            }else {
                isAble = false;
                break;
            }
        }
        
        if(isAble) System.out.println(result);
        else System.out.println(0);
    }
    
    public static boolean isVPS(String c, String target) {
        if(c.equals(target)) return true;
        return false;
    }
    
    // 두 괄호가 아니면 무조건 숫자이다.
    public static boolean isNumber(String str) {
        if(str.equals(")") || str.equals("]")) return false;
        return true;
    }
}