[백준] 2504. 괄호의 값
문제를 처음 보자마자 스택을 써야겠다는 생각이 들었다. 하지만 곱셈과 덧셈을 하려니 순서가 막막했다. 아래 과정 중 3,4 번 과정을 생각해내는게 매우 힘들었던 문제이다.
(()[[]])([])를 예시로 들면 2X(2+3X3) + 2X3 의 값 28이 나온다. 여기서 분배법칙으로 풀어야 알고리즘을 더 쉽게 접근할 수 있다. (2X2 + 2X3X3 + 2X3)
알고리즘 과정
-
반복문을 통해 각각의 문자를 읽는다.
-
중괄호, 대괄호 중 시작하는 괄호가 나오면 스택에 저장하고, tmp라는 변수에 2 또는 3의 값을 곱해서 누적한다.
- ')'가 나오면 스택이 비어있는지 확인하고, 스택의 탑이 '('인지 확인한다.(올바르지 않은 괄호열 확인)
- 현재 문자의 직전 문자가 '('이면 sum변수에 tmp 값을 누적 시킨다.
- tmp 값을 2로 나눈다.
-
3번 과정을 ']'로 반복한다.
-
3, 4 과정을 반복
-
스택이 비어 있지 않거나 올바르지 않은 괄호열이면 0 반환, 아니면 sum 반환한다.
#include <iostream>
#include <stack>
using namespace std;
int main() {
string str;
cin >> str;
int sum = 0, tmp = 1;
bool error = false;
stack<char> st;
for (int i = 0; i < str.size(); i++) {
if (str[i] == '(') {
tmp *= 2;
st.push(str[i]);
}
else if (str[i] == ')') {
if (st.empty()) {
error = true;
break;
}
if (st.top() == '(') {
st.pop();
if (str[i - 1] == '(')
sum += tmp;
tmp /= 2;
}
else {
error = true;
break;
}
}
else if (str[i] == '[') {
tmp *= 3;
st.push(str[i]);
}
else if (str[i] == ']') {
if (st.empty()) {
error = true;
break;
}
if (st.top() == '[') {
st.pop();
if (str[i - 1] == '[')
sum += tmp;
tmp /= 3;
}
else {
error = true;
break;
}
}
}
if (error || !st.empty()) {
cout << 0;
return 0;
}
cout << sum;
}
Author And Source
이 문제에 관하여([백준] 2504. 괄호의 값), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pkpete/백준-2504.-괄호의-값저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)