[java] 백준 알고리즘 2504번 괄호의 값 풀이

이 문제는 스택을 활용해서 푸는 문제다.

괄호를 숫자로 변환해서 스택에 담아두고 총합을 구하는 원리로 풀었다.

예제 같은 경우를 푼 방식을 보자면,

'(()[[]])([])' 처음 입력된다.

처음 '('가 오면 스택에 '('를 담는다. 다음도 '(' 이므로 다시 스택에 '('를 담아준다.

여기까지 스택의 모양은 '((' 이다.  

다음 ')' 가 온다. 닫혔다는 건 괄호 하나가 완성 됐다라는 뜻이다. 그래서 앞에 왔었던 값을 체크해줘야 하는데,

만약, '()'형태로 앞의 문자가 '(' 였다면 바로 2로 변환해주면 된다. 

앞의 문자 '('는 pop을 시켜서 없애준다.

다음은 '(()[[]])([])' 중에서 (()[ 까지 왔다.

'['이 올 경우도 '('와 똑같이 처리하고 점수만 다르게 해주면 된다. 

열리는 네모 괄호라서 바로 다음으로 넘어가면 다시 한번 '['가 나오고,

']'로 닫힌다.

 ---------->  

다음 다시 ']' 괄호로 닫힌다.

'[' 와 ']' 사이에 값이 있으므로 x3을 해준다.

----------> 

다음 ')'가 온다 

그럼 스택 안의 숫자를 모두 더한 값에 x2를 해주면 될 것이다.

---------->

그럼 예시에서 '(()[[]])([])' 중 '(()[[]])' 까지 완성했다.

나머지도 같은 원리로 '([])'는 6이 나올 것이다. 

그럼 답이 28

소스에서는 이 방식으로 구하되, 괄호가 제대로 된 모양으로 완성되지 않았을 경우,

'0'을 출력시키고 있다. 열리고 닫히는 괄호의 총 수가 0이 되어야 한다.

(열릴 경우 +, 닫힐 경우 - 를 해준다)

음수가 되는 순간 닫히는 괄호가 하나 더 있다거나 열린 괄호가 있지도 않은데 닫힌 괄호가 있다는 뜻이기 때문이다.

* 풀이 소스

 
public class Baekjoon2504 {
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        String bracket = st.nextToken();
        Stack<String> stack = new Stack<>();
        int roundBracket = 0;
        int squareBracket = 0;
        
        for(int i=0; i<bracket.length(); i++) {
            
            switch (bracket.charAt(i)) {
            
            case '(':
                roundBracket++;
                stack.push("(");
                break;    
            case ')':
                roundBracket--;
                if(roundBracket > -1) {
                    
                    if(stack.peek().equals("(")) {
                        stack.pop();
                        stack.push("2");
                    }else {
                        int roundResult = 0;
                        
                        while(!stack.isEmpty()) {
                            
                            if(stack.peek().equals("[")) {
                                bw.write("0");
                                bw.flush();
                                return;
                            }else if(stack.peek().equals("(")) {
                                stack.pop();
                                roundResult *=2;
                                stack.push(String.valueOf(roundResult));
                                break;
                            }else {
                                roundResult += Integer.parseInt(stack.pop());
                            }
                            
                        }
                    }
                }
                break;
            case '[':
                squareBracket++;
                stack.push("[");
                break;
            case ']':
                squareBracket--;
                
                if(squareBracket > -1) {
                    if(stack.peek().equals("[")) {
                        stack.pop();
                        stack.push("3");
                    }else {
                        int squareResult = 0;
                        
                        while(!stack.isEmpty()) {
                            
                            if(stack.peek().equals("(")) {
                                bw.write("0");
                                bw.flush();
                                return;
                            }else if(stack.peek().equals("[")) {
                                stack.pop();
                                squareResult *=3;
                                stack.push(String.valueOf(squareResult));
                                break;
                            }else {
                                squareResult += Integer.parseInt(stack.pop());
                            }
                        }
                    }
                }
                break;
            }
            
            if(squareBracket < 0 || roundBracket < 0) {
                bw.write("0");
                bw.flush();
                return;
            }
        }
        
        if(squareBracket != 0 || roundBracket != 0) {
            bw.write("0");
            bw.flush();
            return;
        }
        
        int output = 0;
        
        while(!stack.isEmpty()) {
            output += Integer.parseInt(stack.pop());
        }
        
        bw.write(String.valueOf(output));
        bw.flush();
    }
 
}