백준 2502번 괄호의 값
문제 해설
괄호가 제대로 완성되었는 지 확인하는 것보다 다중 괄호를 어떻게 처리할 것인가가 문제의 핵심이다.
괄호를 완성 여부를 파악할 수 있는 스택을 기반으로 문제를 풀이했다.
- 괄호의 완성 여부 확인
괄호를 하나씩 확인 (반복문)
여는 괄호( ‘ { ‘, ‘ [ ‘ )이 나올 경우 스택에 push 만약 닫는 괄호가 나올 경우 스택의 top 확인.- 스택이 비었다면 이는 불완전한 괄호.
- 스택의 top이 짝이 안 맞는 괄호면 불완전한 괄호
- 짝이 맞다면 괄호 완성.
-
다중 괄호 처리
1번에서 여는 괄호일 경우 스택에 넣어주었다.
그렇다면 다중 괄호일때는 어떻게 될까? ‘ {{ }} ‘ 로 생각해보자.
여는 괄호가 두 개이므로 스택에는 ‘ {{ ‘ 이렇게 들어가 있을 것이다.
다음 괄호는 닫는 괄호이므로 스택에서 pop할 것이다.
하지만 여전히 스택에는 여는 괄호 하나가 남아있다.
즉, 괄호가 완성되었을 경우, pop를 하고도 여전히 스택이 비어있지 않다면 이는 다른 괄호 안에 속해 있다는 것이다. - 괄호의 값 계산
이제 다중 괄호의 특성을 알았으니 값을 계산해보자.
단일 괄호의 경우, {} 2점, [] 3점이다. 그러나 다중 괄호일 경우 단순 더하기가 아니라 포함 괄호 값의 곱하기 * (2,3)점이다.
이런 특성을 생각해서 괄호마다 점수를 계산한다.
해법: 스택에 괄호뿐만 아니라 괄호의 값도 같이 push한다.
기본적으로 괄호의 값을 1로 넣는다. 괄호가 완성되면 2,3를 곱하면 되기 때문이다.
단일 괄호의 경우 answer라는 변수에 완성된 괄호의 값 추가.
다중 괄호의 경우 스택에 이미 괄호가 있으므로 스택 top에 있는 괄호의 값을 수정한다.
괄호의 값이 1이라면 완성된 괄호의 값 할당, 1이 아니라면 기존 값 + 완성된 괄호 값
이해하기 쉽게 ‘[ ] { { } } ‘ 예시를 보자.
답을 저장하기 위한 변수 answer라 가정
[ ] 차례:
여는 괄호 [ 를 스택에 push
닫는 괄호와 스택의 top이 같으므로 단일 괄호 완성 1*3이다.
스택이 비었으므로 answer += 3.
{ { } } 차례:
여는 괄호 {, { 스택에 push
닫는 괄호와 스택의 top이 같으므로 단일 괄호 완성되어 괄호의 값 1*2.
스택에 괄호가 남아 있다. 스택에 남아 있는 괄호의 값이 1이므로 pop하고 괄호의 값을 2으로 바꾸어 다시 push해준다.
{ } 남은 괄호 차례 :
다시 괄호 완성되어 괄호의 값 2 * 2
스택이 비었으므로 answer += 4
이렇게 정답은 총 7이 된다.
소스코드
#include <iostream>
#include <stack>
#include <utility>
// 백준 2504번 괄호의 값
using namespace std;
// 1. 괄호는 스택 사용에 기반
// 2. 괄호 안에 괄호에 대한 계산 필요.
// 2-1. 기본적인 계산 = ()이면 2점 []이면 3점 계산. 괄호가 완성될 경우 2,3점 계산
// 2-2. 괄호 안 괄호일 경우 스택에 하나 이상 쌓여져있다. => 괄호 완성된 후 스택이 empty가 아니라면 완성된 점수 더하기(쌓여져있는 괄호의 점수가 1점이라면 완성된 점수를 할당)
// 3. pair를 이용해 스택 쌓기.
// 4. 만약 모든 과정 후 스택이 비어있지 않다면 괄호 불완전.
int main() {
string p;
cin >> p;
// 1 + 3.
stack<pair<char, int>> st;
int answer = 0;
for (int i = 0; i < p.length(); i++) {
// 1.
if (p[i] == '(' || p[i] == '[') {
st.push({ p[i],1 });
}
else {
// 1.
if (st.empty()) {
answer = 0;
break;
}
char open = st.top().first;
if (p[i] == ')' && open == '[') {
answer = 0;
break;
}
else if (p[i] == ']' && open == '(') {
answer = 0;
break;
}
// 2.
else {
int val = st.top().second;
st.pop();
// 2-1.
if (p[i] == ')' && open == '(') {
val *= 2;
}
else {
val *= 3;
}
// 2-2. 괄호 안 괄호
if (!st.empty()) {
pair<char, int> pi = st.top();
if (pi.second == 1)
pi.second = val;
else
pi.second += val;
st.pop();
st.push(pi);
}
// 2-2. 괄호 안 괄호가 아니라면
else
answer += val;
}
}
}
// 4.
if (!st.empty())
answer = 0;
cout << answer << endl;
return 0;
}