백준 2504 - 괄호의 값

문제링크

• 백준 2504

문제설명

• ’(‘ , ‘)’ , ‘[’ , ‘]’ 로 이루어진 괄호 문자열이 주어진다.
• ’()’ 괄호열은 값이 2이고, ‘[]’ 괄호열은 값이 3이다.
• 모든 괄호가 올바르게 열리고 닫혔다면 올바른 괄호열이 되고, 값을 계산할 수 있다.
  • 괄호 안에 괄호가 있는 경우 곱하기, 완성된 괄호끼리는 더하기 연산을 진행한다.
  • 예를 들어, (()[[]])([]) 의 경우 2x(2+3x3) + (2x3) = 28 이다.
• 주어진 괄호열이 올바른 괄호열이면 수식이 결과값을 출력하고, 올바르지 않은 괄호열이면 0을 출력하라.

문제접근

• 계산에 우선순위가 존재하기 때문에 앞에서부터 무작정 계산할 수 없고, 중간에 계산된 결과값이 다시 수식에 적용되어야 하기 때문에 재귀호출을 통한 접근을 생각했었다.
• 하지만, 일관된 계산로직을 찾아내기 어려웠고, 괄호열에서 흔히 사용되는 스택 자료구조로 접근을 해보았다.
• 앞에서부터 미리미리 계산이 될 수 있도록 괄호가 적용된 수식을 분배법칙을 통해 풀어냈다.
  • 2x(2+3x3)+(2x3) = 2x2 + 2x3x3 + 2x3
• 이제 순차적으로 접근하며 오른쪽 괄호가 등장했을 때마다 결과를 계산해주면 된다.
• 오른쪽 괄호가 들어오면 매칭되는 괄호의 값을 변수 tmp 에 곱해두고 스택을 pop 해준다.
• 오른쪽 괄호 다음에 들어오는 괄호가 왼쪽 괄호라면 두 괄호열의 연산은 덧셈관계로 바뀌어야 한다. 따라서, 곱해진 값들을 모두 더해주고 다음으로 넘어가야하는데 이때, 스택에 남아있는 괄호가 있다면 먼저 모조리 곱해주고 더해주어야 한다.

구현

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

bool checkValidString(string str) {
	stack<char> s;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(' || str[i] == '[') s.push(str[i]);
		else {
			if (s.size() == 0) return false;
			if (str[i] == ')' && s.top() != '(') return false;
			else if (str[i] == ']' && s.top() != '[') return false;
			else {
				s.pop();
			}
		}
	}
	if (s.size() != 0) return false;
	return true;
}

// 제거되지 못한 괄호 값을 곱해준다.
int remainStackValue(stack<char> s) {
	int ret = 1;
	while (!s.empty()) {
		if (s.top() == '(') ret *= 2;
		else if (s.top() == '[') ret *= 3;
		s.pop();
	}
	return ret;
}

// 분배법칙이 적용된 계산 로직
int getValue(string str) {
	stack<char> s;
	int ans = 0;
	int tmp = 1;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(' || str[i] == '[') s.push(str[i]);
		else if (str[i] == ')' || str[i]==']') {
			if (str[i] == ')') tmp *= 2;
			else if (str[i] == ']') tmp *= 3;
			s.pop();
			if (i + 1 < str.length()) { 
				// 오른쪽 괄호 다음이 왼쪽 괄호인 경우 값을 더한다.
				if (str[i + 1] == '(' || str[i + 1] == '[') {
					tmp *= remainStackValue(s);
					ans += tmp;
					tmp = 1;
				}
			}
		}
	}
	ans += tmp;
	return ans;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	string str;
	cin >> str;

	// 올바른 문자열인지 확인
	bool flag = checkValidString(str);
	if (flag == 0) {
		printf("0\n");
		return 0;
	}
	
	int ans = getValue(str);
	printf("%d\n", ans);
	
	return 0;
}