[JAVA]BOJ 2504, 괄호의 값

생각하는게 너무 어려웠다. 스택을 사용한다.

 

1. (, [ 인 경우, stack에 넣고 tmp=*2, tmp=* 3 하기
2. ), ] 인 경우, 2-1.()[]인 경우 res+=tmp, 2-2.아닌경우 tmp/=2,3 하기

 

(()(())) 이걸로 예를 들면.. 우선 숫자로 식을 표현해보자

우리가 일반적으로 보는 숫자 식으로 바꾸면 2*(2+2*(2)) 이 된다.  그리고 분배법칙에 따르면 이 식은 2*2 + 2*2*(2)과 같다. 위에서 설명한 1. 2.방식은 숫자식을 후자( 2*2 + 2*2*(2) )와 같은 방식으로 계산한 것이다. 

한 단계씩 글로 표현하면 아래와 같다.

(()(())) 코드 1개씩 실행할때 변수 바뀌는 모습

코드는 위의 알고리즘대로 짜면 된다. 그리고 괄호가 맞지않을때 에러표시로 0을 출력해야한다. 즉 예외처리가 필요하다. 괄호가 맞지않는 경우는 '[)' 처럼 짝이 안 맞거나 , '((' 또는 '))' 처럼 닫히지 않는 경우이다.

스택으로 표현하면.. 아래와 같다.

1. )(또는 ])를 만나서 stack 제일 위의 값과 비교해야하는데 스택이 비어있음
2. )를 만나서 stack.peek()를 했는데 (가 아님, 짝이 안맞음('[ ]' 인 경우에도..)
3. String 한 바퀴를 돌았는데 stack에 (, [가 남아있음

 

코드를 보면 더 이해가 될거라고 생각한다.

---

아래는 전체 코드이다.

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

public class BOJ2504 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        String str;
        int i, tmp = 1, result = 0;
        char ch;

        str = br.readLine();

        for(i=0;i<str.length();i++){
            ch = str.charAt(i);

            if(ch == '('){
                tmp *= 2;
                stack.add(ch);
            }
            else if(ch == ')'){
                if(stack.isEmpty() || stack.peek() != '('){ // 괄호 올바른지 확인
                    result = 0;
                    break;
                }
                if(str.charAt(i-1) == '('){
                    result+=tmp;
                    tmp/=2;
                    stack.pop();
                }
                else{
                    tmp/=2;
                    stack.pop();
                }
            }
            else if(ch == '['){
                tmp *= 3;
                stack.add(ch);
            }
            else if(ch == ']'){
                if(stack.isEmpty() || stack.peek() != '['){ // 괄호 올바른지 확인
                    result = 0;
                    break;
                }
                if(str.charAt(i-1) == '['){
                    result+=tmp;
                    tmp/=3;
                    stack.pop();
                }
                else{
                    tmp/=3;
                    stack.pop();
                }
            }
        }
        if(!stack.isEmpty()) // 괄호 올바른지 확인
            result = 0;
        System.out.println(result);
    }
}

 

 

 

()
( -> tmp*=2 
) -> tmp/=2 -> () -> res+=2

 

()[]
( -> tmp*=2
) -> res+=tmp -> res=2 -> tmp/=2 -> tmp=1
[ -> tmp*=3
] -> res+=tmp -> res=5 -> tmp/=3 -> tmp=1
res = 5


(())
( tmp*=2
( tmp*=2
) -> ()임 -> res += tmp -> res = 4
) -> ()가 아님 -> tmp/=2


((()))
( tmp*=2 -> tmp=2
( tmp*=2 -> tmp=4
( tmp*=2 -> tmp=8
) -> ()임 -> res+=tmp -> res=8 -> tmp/=2 -> tmp=4
) -> ()가아님 -> tmp/=2 -> tmp=2
) -> ()가아님 -> tmp/=2 -> tmp=1

 

(())()
( tmp*=2 -> tmp=2
( tmp*=2 -> tmp=4
) -> ()임 -> res+=tmp -> res=4 -> tmp/=2 -> tmp=2
) -> ()가아님 -> tmp/=2 -> tmp = 1
( tmp*=2 -> tmp=2
) -> ()임 -> res+=tmp -> res=6 -> tmp/=2 -> tmp=2



(()(()))
( tmp*=2 -> tmp=2
( tmp*=2 -> tmp=4
) -> ()임 -> res+=tmp -> res=4 -> tmp/=2 -> tmp=2
( tmp*=2 -> tmp=4
( tmp*=2 -> tmp=8
) -> ()임 -> res+=tmp -> res=12 -> tmp/=2 -> tmp=4
) -> ()가아님 -> tmp/=2 -> tmp = 2
) -> ()가아님 -> tmp/=2 -> tmp = 1