[백준] BOJ 2504 괄호의 값(자바/스택)

문제 풀이 방법

분배 법칙을 통해 괄호에 대한 연산 처리를 해주어야 하는 문제였습니다.  다음과 같은 예시를 통해 설명드리겠습니다. 

 

조건

다음 조건과 같이 값 * ( XY )가 값 * X + 값 * Y로 계산됩니다.  이는 분배 법칙에서 a(b + c)가 a*b + a*c로 전개되었던 것과 같습니다.  

 

 

 

다음과 같은 예시로 문제 설명을 드리겠습니다.

 

이 경우에는 분배법칙에 따라서 2 * ( 2 + 3 * 3) 가 4 + 2 * 9 = 22가 된다.  

 

따라서, 

 

여는 괄호 '(' , '['인 경우

스택에 넣고, temp = temp * 2 또는 temp =  temp * 3을 진행한다. 

분배 법칙에 따라 곱셈을 하기 위해서이다.

 

닫는 괄호 ')' , ']' 인 경우

먼저, 올바른 괄호인지 확인한다. 올바르지 못하면 break

만약 괄호 짝이 인접하게 붙어있으면 현재까지 누적했던 temp를 결괏값에 반영한다.

 

위의 예시를 토대로 지금 ')' 를 만났으니까 지금까지 누적한  2 * 2를 결괏값에 반영하는 거다.

이후에 괄호를 닫아주는 거니까 temp / 2를 해주면 된다.

 

 

 

 

어려웠던 점

예를 들어 ( ( ) [ [ ] ] )인 경우에 안의 ()와  [ [ ] ]를 더해줘야 하는데 누적해서 어떻게 더해주지 고민했다. 아무래도 논리가 부족하기도 했고, 올바른 괄호에 대한 확인은 구현 가능했으나 그 후 연산 처리인 분배 법칙은 떠오르지도 않았다.

 

 

 

 

---

구현

public class Main_2504 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		Stack<Integer> stack = new Stack<>();//인덱스를 저장
		int result = 0, tmp = 1;
		
		//분배 법칙을 통해 계산함
		for (int i = 0; i < str.length(); i++) {
			if(str.charAt(i) == '(') {
				stack.push(i);
				tmp *= 2;
			}else if(str.charAt(i) == '[') {
				stack.push(i);
				tmp *= 3;
			}else if(str.charAt(i) == ')') {
				if(stack.isEmpty() || str.charAt(stack.peek()) != '(') {
					result = 0;
					break;
				}else if(str.charAt(i-1) == '(') {//인접한 괄호가 여는괄호인 경우
					result += tmp;//현재까지 누적된 값을 결과값에 더해줌
				}
				tmp /= 2;
				stack.pop();
			}else {//']'인 경우
				if(stack.isEmpty()|| str.charAt(stack.peek()) != '[') {
					result = 0;
					break;
				}else if(str.charAt(i-1) == '[') {
					result += tmp;
				}
				tmp /= 3;
				stack.pop();
			}
			
		}
		
		if(!stack.isEmpty()) result = 0;
		
		System.out.println(result);
	}
}