[BOJ] 2504 : 괄호의 값
풀이
스택
스택을 활용해야한다는것은 바로 눈치챘지만,
혼자 손으로 풀어봐도 어떤식으로 해야 값을 분배법칙처럼 계산할 수 있을까 오래 고민했다.
스택에 추가할때 값을 2혹은 3씩 곱하고, pop할때 2혹은 3씩 나누는 계산을 하면 된다.
키포인트는 문제에 쓰여있는 ‘([)]’는 올바른 괄호열이 아니라는것.
즉 반드시 () 혹은 [] 가 나오게된다.
그때 지금까지 곱했던 값을 sum변수에 추가해주면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <stack>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string a;
cin >> a;
stack<char> s1;
stack<char> s2;
int sum = 0;
int cur = 1;
int flag = 0;
for (int j = 0; j < a.size(); j++) {
if (a[j] == ')') {
if (s1.empty()) {
flag = 1;
break;
}
cur /= 2;
s1.pop();
}
else if (a[j] == ']') {
if (s2.empty()) {
flag = 1;
break;
}
s2.pop();
cur /= 3;
}
else if(a[j]=='('){
if (j < a.size() - 1 && a[j + 1] == ')') {
sum += cur * 2;
j++;
}
else {
cur *= 2;
s1.push(a[j]);
}
}
else if(a[j]=='['){
if (j < a.size() - 1 && a[j + 1] == ']') {
sum += cur * 3;
j++;
}
else {
cur *= 3;
s2.push(a[j]);
}
}
}
if (flag || !s1.empty() || !s2.empty()) {
cout << 0;
}
else {
cout << sum;
}
return 0;
}
Written on March 17, 2019