[BOJ] 백준 2504번 : 괄호의 값 C++ : 아주정은

내가 어떻게 풀었는지 기록할려고 쓴다.

​문제는 문자열을 받았을때, 문자열을 숫자로 변환하는게 문제다.

그럼 일단 문자열을 입력 받는게 우선이다.

문자열을 입력받고, 문자열을 반복문을 통해 하나하나 읽어 나간다.

경우의 수는 네가지이다. (,),[,] 이렇게 네가지로 나누어서 처리를 해준다.

근데 나는 처음에 ),] 이 닫아주는 문자열이 나올때 숫자를 업데이트 할려고했다.

예를 들면, (()[[]]) = 2*(2+3*(3)) = 22 이다. 그런데 분배법칙으로 풀면 2*2 + 2*3*3 이렇게 나온다.

내 생각이 짧았다. 분배법칙이 가능하기때문에 tmp 변수를 초기에 1로 두고, 괄호를 열어주는 문자가 나오면 곱해주면서 분배법칙이 잘적용될수있는 파라미터를 만든다. 그러다가 닫아주는 문자가 나오면 tmp를 결과값에 더해주고 나눠준다.

그리고 나머지 에러들을 처리해준다. 만약 잘못된물자열이라면 짝이 안맞을 것이다. 스택에서 나오는게 현재 문자와 짝이 안맞을 경우, 문자열이 끝나지 않았는데 스택이 비어버리는 경우, 문자열이 끝났는데 스택에 남아있는 경우가 있을것이다.

솔직히 이해는 되지만 말로 설명하기는 좀 힘들다.

​알고리즘 문제는 많이 풀어보면서 외우는것도 좋은 방법인것같다.

#include <iostream>
#include<stack>
#include<string>

using namespace std;


int main()
{
	int tmp = 1, output = 0;
	string str;
	bool wrong = false;
	stack<char> st;
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(') {
			st.push('(');
			tmp *= 2;
		}
		else if (str[i] == '[') {
			st.push('[');
			tmp *= 3;
		}

		else if (str[i] == ')') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '(') {
				if (str[i - 1] == '(') output += tmp;
				st.pop();
				tmp /= 2;
			}
			else {
				wrong = true;
				break;
			}
		}
		else if (str[i] == ']') {
			if (st.empty()) {
				wrong = true;
				break;
			}
			if (st.top() == '[') {
				if(str[i-1]=='[') output += tmp;
				st.pop();
				tmp /= 3;
			}
			else {
				wrong = true;
				break;
			}
		}
	}

	if (wrong or !st.empty()) {
		cout << 0 << endl;
	}
	else {
		cout << output << endl;
	}
}
​