[문제] 백준 2504번 괄호의 값

www.acmicpc.net/problem/2504

2504번: 괄호의 값

내 풀이

 

예시 문제를 직접 연산식으로 나타내면 아래와 같다.

연산식을 분배하면 2*2 + 2*3*3 + 2*3 이 되는데, 이 때 더해지는 시점을 보면 

화살표로 표시한, 열고 닫는 괄호가 바로 나오는 때라는 걸 알 수 있다.

 

 2*2 + 2*3*3 + 2*3 

빨간 부분은 화살표 시점의 괄호 값이다.

그리고 그 앞에 누적되서 곱해진 것은 해당 괄호쌍 앞에 누적된 열린 괄호만큼이다.

따라서, 이 논리로 아래 코드와 같이 스택으로 구현하면 답을 구할 수 있다..

public class BOJ_2504 {
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	
		String s = in.readLine();	//괄호열

		Stack<Character> stack = new Stack<>();	//여는 괄호 담을 스택

		int res = 0;	//결과값 저장
		int plus = 1;	// 계속해서 결과값에 더해질 변수 (누적곱)
		boolean isRight = true;	// 올바른 괄호열인지 판단

		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);

			// 스택 비었는데 닫힌 괄호 들어오면 잘못된 괄호열
			if (stack.isEmpty()) {
				if (c == ')' || c == ']') {
					isRight = false;
					break;
				}
			}
			// 여는 괄호열 => push. 괄호에 해당하는 숫자를 plus숫자에 곱해준다. 
			if (c == '(') {
				stack.push(c);
				plus *= 2;
			} else if (c == '[') {
				stack.push(c);
				plus *= 3;
			} 
			
			// 짝이 맞는 괄호가 스택에 있을 때
			else if (c == ')' && stack.peek() == '(') {
				// () 가 나왔을 떄 결과값에 더해준다.
				if (s.charAt(i - 1) == '(') {
					res += plus;
				}
				//짝이 맞으니 하나 pop
				stack.pop();
				// 더해줄 변수에 자기만큼 나눠줌 
				plus /= 2;
			} else if (c == ']' && stack.peek() == '[') {
				if (s.charAt(i - 1) == '[') {
					res += plus;
				}
				stack.pop();
				plus /= 3;
			}
			// 나머지 경우 -> 올바르지 않은 괄호열
			else {
				isRight = false;
				break;
			}
		}
		//올바르지 않은 괄호열 == 스택에 괄호가 남아있거나 위에서 isRight가 false가 된 경우
		if (!stack.isEmpty() || !isRight) 
			res = 0;
		
		System.out.println(res);
	}
}