[BOJ] 백준 2504번 괄호의 값 (Java)

#2504 괄호의 값

난이도 : 실버 2

유형 : 자료구조/ 스택

2504번: 괄호의 값

▸ 문제

4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.

1. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 
2. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. 
3. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.

예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. 

1. ‘()’ 인 괄호열의 값은 2이다.
2. ‘[]’ 인 괄호열의 값은 3이다.
3. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
4. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
5. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.

예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.

여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다. 

▸ 입력

첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.

▸ 출력

첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.

 

 

문제 풀이  

기본적인 문제의 본질은 간단한 데 어떻게 구현하느냐가 까다로웠다. 문제만 읽었을 때는 쉬워보였는데 나름 생각을 많이하게 만드는 문제였다.

 

초기 아이디어는 다음과 같았다.

1. (', '['를 만나면 st에 해당 괄호를 저장한다.
2. ')'을 만난다.
   1. st 앞에 숫자가 있으면 괄호가 닫힐 때 까지 ('('를 만날 때까지) 숫자들을 곱해준다.
   2. '('를 만나면 해당 숫자를 곱해주고 저장해준다.
3. ']'을 만난다.
   1. st 앞에 숫자가 있으면 괄호가 닫힐 때 까지 ('['를 만날 때까지) 숫자들을 곱해준다.
   2. '['를 만나면 해당 숫자를 곱해주고 저장해준다.
4. st.peek()과 그 다음 값이 숫자라면 값을 더해준다.

 

초기 아이디어

 

그런데 반례가 있었다. 만약 stack에 숫자와 괄호를 동시에 저장해놓으면 나중에 가서 '(', '['가 숫자인지 괄호인지 구분을 못하게 된다.

컴파일러가 각 괄호를 '(' :40, '[':41 인 숫자로 인식하여 처리하기 때문이다.

 

반례

(((()))(([])))(([[]]))[]() 

해당 연산은 앞에 40까지 계산하게 되면 (로 인식하여 로직이 돌아간다. 그래서 괄호를 닫을 때 하나 더 인식해서 에러처리가 된다. 이 부분에 대해 예외처리를 해줘야 하는데 그러면 코드가 점점 산으로 갈 것 같았다.

 

( ((())) (([])) ) : 2(8+12) = 40

(([[]]))[]() = 36+3+2 = 41 

정답 : 81

오답 : 0 

 

오답 코드 펼쳐보기↓ (37% 오답)

import java.io.*;
import java.util.Stack;

public class Main {

	static boolean flag;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();

		Stack<Character> st = new Stack<>();
		flag = true; 
		if(line.length()/2 == 1) flag=false;
		for(int i=0; i<line.length(); i++) {
			char cur = line.charAt(i);
			if(flag) {
				if(cur == '(') {
					st.push(cur);
				}
				else if(cur == '[') {
					st.push(cur);
				}
				else if(cur == ')') {
					check(st, cur);
				}else if(cur == ']') {
					check(st, cur);
				}
				else {
					flag = false;
					break;
				}
				
				if(!st.isEmpty() && st.peek()!='(' && st.peek()!='[') {
					int f = st.pop()-48;
					int num = f;
					while(!st.isEmpty() && st.peek()!='(' && st.peek()!='[') {
						if(st.peek() =='2' || st.peek() =='3') {
							int tmp = st.pop()-48;
							num += tmp;
						}else break;
					}
					char putNum = (char)(num+48);
					st.push(putNum);
				}
			}
				
		}
		
		if(!flag) {
			System.out.println(0);
		}else {
			int answer=0;
			while(!st.isEmpty()) {
				int num = (int)(st.pop()-48);
				if(num >0) answer += num;
				else {
					System.out.println(0);
					return;
				}
			}
			System.out.println(answer);
		}
	}
	
	static void check(Stack<Character> st, char cur) {
		
		if(!st.isEmpty() && (st.peek() == '(' || st.peek() == '[') ) {
			if(cur==')' && st.peek()=='(') {
				st.pop();
				st.push('2');
				return;
			}
			else if(cur==']' && st.peek()=='[') {
				st.pop();
				st.push('3');
				return;
			}else {
				flag = false;
				return;
			}
		}
		else {
			int tmp = 0;
			if(!st.isEmpty() &&st.peek()!='(' && st.peek()!='[') {
				tmp = st.pop()-48;
				
				if(!st.isEmpty()) {
					if(cur==')' && st.peek()=='(') {
						tmp *= 2;
					}
					else if(cur==']' && st.peek()=='[') {
						tmp *= 3;
					}else {
						flag=false;
						return;
					}
					st.pop();
				}
			}else {
				flag = false;
				return;
			}
			char putNum = (char)(tmp+48);
			st.push(putNum);
		}
	}
}

 

 

그래서 구현을 하다가 이 방식은 도무지 아닌 것 같아서 아이디어를 갈아엎었다. 괄호의 아스키코드랑 숫자랑 혼동되기 때문에 스택에 연산되는 숫자를 저장해주지 않고 따로 데이터를 다뤄야한다. 분배법칙이라는 힌트를 얻고 다시 새롭게 작성하여 풀이하였다.

 

분배법칙

해당 연산은 결국 2*(2+ 3*3) + 2*3이다. 그러면 괄호가 닫힐 때마다 현재까지의 곱을 곱해주면 되는 것이다. 괄호가 닫히기 시작하면 해당  저장해놓은 값들을 answer데이터에 옮기고 나머지 괄호가 닫힐 때마다 저장해놓은 곱셈 값들을 정리해준다. 

구상

1. '(', '['를 만나면 st에 해당 괄호를 넣고 각 2,3의 값을 tmp에 곱해준다.
2. ')'을 만난다.
   1. st가 비어있거나 st.peek() == '('이 아니면 올바른 괄호가 아니므로 에러
   2.  st.peek() == '('
      1. 바로 이전 값이 ')'이면 지금까지 저장해놓은 값을 answer에 저장해준다. answer += tmp
      2. 괄호가 닫힐 때마다 저장해준 값들을 정리해준다. tmp /= 2
3. ']'을 만난다.
   1. st가 비어있거나 st.peek() == '['이 아니면 올바른 괄호가 아니므로 에러
   2.  st.peek() == '[' 
      1. 바로 이전 값이 ']'이면 지금까지 저장해놓은 값을 answer에 저장해준다. answer += tmp
      2. 괄호가 닫힐 때마다 저장해준 값들을 정리해준다. tmp /= 3
4. 결과값을 출력해준다.
   1. 에러이거나 st이 비어있지 않으면 0 출력
   2. 올바른 괄호일 경우 answer 출력

풀이 코드 

import java.io.*;
import java.util.Stack;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = br.readLine();

		Stack<Character> st = new Stack<>();
		boolean flag = true; 
		int answer = 0;
		int cnt =1;
		for(int i=0; i<line.length(); i++) {
			char cur = line.charAt(i);
			if(cur == '(') {
				st.push(cur);
				cnt *= 2;
			}
			else if(cur == '[') {
				st.push(cur);
				cnt *= 3;
			}
			else {
				if(cur == ')') {
					if(st.isEmpty() || st.peek() != '(') {
						flag=false;
						break;
					}
					if(line.charAt(i-1) =='(') {
						answer += cnt;
					}
					st.pop();
					cnt /= 2;
				}else if(cur==']') {
					if(st.isEmpty() || st.peek() != '[') {
						flag=false;
						break;
					}
					if(line.charAt(i-1)=='[') {
						answer += cnt;
					}
					st.pop();
					cnt /= 3;
				}
				else {
					flag = false;
					break;
				}
			}
		}
		if(!flag || !st.isEmpty()) {
			System.out.println(0);
		}else {
			System.out.println(answer);
		}
	}
}