[백준] 2504. 괄호의 값 (자바 JAVA)

[ 문제 ]  BOJ 2504. 괄호의 값

 

문제 링크 : 

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

2504번: 괄호의 값

 

 

---

# 접근 방법 및 풀이 

 

• 와 이게 무슨 실버 2야..? 너무 충격받은 문제다. 이런게 코테에 나오면 끔직 그자체다. 생각하는데 너무 시간이 오래 걸렸고, 한번만에 풀지 못해서 인터넷에 찾았다. 그리고 그걸 이해하는데도 시간이 오래 걸렸다ㅠㅠ
• 일단 분배 법칙을 바로 떠올렸다면 풀어볼만한 문제다.
• 스택을 이용해서 풀었고, 올바른 괄호열인지 아닌지 체크하는건 어렵지 않아서 올바른 괄호열이 아니라면 0을 출력하는 것 까진 접근했다. 이후는 숫자 계산의 문제다. 
• 예를들어, ()()는 2+2 이고, (())는 2*2 이다. 여기까진 쉽다.
• ( ( ) [ ] ) 라면, 이걸 숫자로 대입하면 2*( 2 + 3) 이렇게 풀이가 된다. 그리고 이걸 분배법칙을 적용해서 식을 풀면, 2*2 + 2*3이다. 
• 마찬가지로 예제 1번의 ( ( ) [ [ ] ] ) 이부분을 숫자로 대입하면, 2 * (2 + 3 * 3)이 되고, 분배법칙을 적용해서 식을 풀면, 4 + 6 * 3 = 4 + 18 = 22가 된다. 
• 이걸 생각하고 코드를 짜면 되는데, 가장 먼저 arr[] 문자 배열에 입력을 받고 길이만큼 탐색한다.
• 문자가 '('나 '[' 일 경우는 스택에 push하고 tmp에 '('일경우는 2를 곱하고 '['일경우는 3을 곱한다.
• 문자가 ')' 나 ']' 일 경우엔 올바른 괄호열인지 체크하고, ans에 tmp를 더해주고 다시 ')'나 ']'에 맞춰 2 or 3으로 tmp를 다시 나눠준다.
• 근데 이때, 그냥 무조건 ans에 tmp를 더해주는게 아니라, 입력받은 arr[] 배열에서 현재 idx바로 전 idx-1 문자가 여는 괄호일 경우에만 더해줘야 한다.
• 예를들어, arr[] 이 다음과 같을 경우에는 

• 0	1	2	3	4	5
  [	[	[	]	]	]
  tmp : 3	9	27	9	3	1

• idx가 3인 순간에 닫는 괄호를 만나 지금까지의 tmp를 ans에 더할 것이다. 그럼 ans는 27이되고 더이상 ans에 값이 더해지면 안된다. 이때 더해지는 순간은 idx-1인 arr[2]가 여는 괄호일때만 지금까지 곱한 값을 더해주는 것이다.
• idx가 4인 순간 또 닫는 괄호를 만나서 tmp인 9를 더하는게 아니라, arr[3]이 여는 괄호가 아니기 때문에 더해줄 필요없이 tmp를 나눠주기만 하면 된다.

# 주의할 점 

• 분기가 많기때문에 올바른 괄호열인지 잘 확인해야하고, tmp가 더해지는 순간과 아닌 순간을 잘 나누어야한다.
• 이걸 이해 못해서 무려..3시간이나 썼다. 부끄럽지만, 이해했으니까 다음에 비슷한 문제가 나오면 이렇게 접근해서 풀어봐야 겠다.

 

JAVA 코드

package Silver;

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

public class bj2504_괄호의값 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<>();
		char arr[] = in.readLine().toCharArray();
		int ans = 0;
		int tmp = 1;
		for (int i = 0; i < arr.length; i++) {
			char c = arr[i];
			if(c == '(' || c == '[') { // (, [ 일 경우
				stack.add(c);
				tmp *= (c=='(')? 2: 3;
			}
			else { // ), ]일 경우
				if(stack.isEmpty()) {
					ans = 0;
					break;
				}else {
					char cc = stack.pop();
					if(c == ')') {
						if(cc != '(') {
							ans = 0;
							break;
						}else {
							if(arr[i-1] == '(')
								ans += tmp;
							tmp /= 2;
						}	
					}else {
						if(cc != '[') {
							ans = 0;
							break;
						}else {
							if(arr[i-1] == '[')
								ans += tmp;
							tmp /= 3;
						}
					}
				}			
			}
			//System.out.println(tmp + " ans는" + ans);
		}//end for
		if(!stack.isEmpty())
			ans = 0;
		System.out.println(ans);
	}
}

 

 

 

REVIEW

정말 좋은 문제.. 이거 왜 실버일까?