[백준] 2504번: 괄호의 값

스택을 이용한 괄호쌍 문제의 응용이다. 단순히 괄호 간에 짝이 맞는지를 판단하는 것에 더하여 각 괄호마다 가중치를 두어 덧셈 및 곱셉으로 전체 값을 계산해야 한다.

solved.ac 기준 실버1 티어 문제임에도 처음 문제를 봤을 때 바로 풀지 못했고, 다른 분들의 코드를 여러 개 참고한 뒤에야 확실히 이해할 수 있었다.

이 문제의 핵심은 분배법칙이다.

괄호 안의 계산식을 다 계산하고 나서 이것을 다시 괄호 밖의 가중치와 곱하는 방식이 아닌, 처음부터 가중치를 괄호 안의 식에 곱한 뒤에 계산해야 하는 것이다.

문제에서 주어진 입력을 읽어나갈 때 발생 가능한 경우의 수는 이렇다.

1. 현재 문자가 "(" 또는 "["일 때
   => 그냥 스택에 push한다.
2. 현재 문자가 ")"일 때
   2-1. 스택이 비었을 때
   => 입력이 잘못된 경우이므로 break.
   2-2. 스택의 top이 "("일 때
   => "()"이므로 스택을 한 번 pop하고 "2"를 push한다.
   2-3. 스택의 top이 숫자일 때
   => 괄호 안에 식이 있는 경우이다. 숫자가 다 떨어질 때까지, 즉 여는 괄호를 만날 때까지 해당 숫자에 가중치 2를 곱하고 임시 변수에 더해나간다.
   => 모든 숫자를 더했다면 스택에 남아있는 여는 괄호를 pop하고 임시 변수를 push한다.
   => 만약 스택이 비었거나 "["이 남아있는 경우 잘못된 입력이므로 break.
3. 현재 문자가 "]"일 때
   => 2번과 비슷하게 처리한다. 가중치는 2 대신 3을 쓰면 된다.

2-3번이 이 문제에서 중요한 부분이다.
같은 레벨 안에서, 서로 더하기로 연결되어 있는 숫자에 현재 괄호의 가중치만큼을 각각 곱해주면서 덧셈을 처리하는 것과 같은 동작이다.

입력 문자열을 끝까지 읽었다면 스택에는 가장 바깥쪽의 숫자(식)들이 남아있게 되므로, 이것들을 모두 더한 후 출력해주면 된다.

풀이 코드 (C++)

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


int main() {
	stack<string> s;
	string input, cur;
	int result = 0;

	cin >> input;

	for (int i = 0; i < input.length(); i++) {
		cur = input.at(i);

		// 여는 괄호가 나오면 그냥 push
		if (cur == "(" || cur == "[") {
			s.push(cur);
			continue;
		}
		
        // 닫는 괄호가 나왔는데 스택이 비었을 때
		if (s.empty()) {
			break;
		}

		// "()" 또는 "[]" = 2 또는 3으로 대체
		if (cur == ")" && s.top() == "(") {
			s.pop();
			s.push("2");
			continue;
		} else if (cur == "]" && s.top() == "[") {
			s.pop();
			s.push("3");
			continue;
		}

		int temp = 0;
		int mul = cur == ")" ? 2 : 3; // 분배법칙 사용 시 가중치

		// 스택에서 숫자를 꺼내면서 가중치만큼 곱하고 서로 더해나감
        // ex) 3*(12+4+7) = 3*12 + 3*4 + 3*7
		while (!s.empty() && s.top() != "(" && s.top() != "[") {
			temp += stoi(s.top()) * mul;
			s.pop();
		}
		
        // 입력이 잘못된 경우
		if (s.empty() || (cur == ")" && s.top() == "[") || (cur == "]" && s.top() == "(")) {
			// Error
			break;
		}

		// 모든 식을 처리했다면 push
		s.pop();
		s.push(to_string(temp));
	}

	// 마지막 남은 숫자들을 더해줌
	while (!s.empty()) {
		if (s.top() == "(" || s.top() == "[") {
			result = 0;
			break;
		}
		result += stoi(s.top());
		s.pop();
	}

	cout << result;
}