[BOJ/C++] 2504: 괄호의 값

🥈 Silver 1

✏️ 1차 솔루션

⭐️ 스택으로 풀이
1. '(', '[' ➡️ 괄호 스택에 push
2. ')', ']'
1) 스택이 비어있을 경우 0 return
2) 스택의 top 값과 짝이 맞지 않다면 0 return
3) 스택의 top 값이 기존에 계산한 결과를 저장한 숫자('x')라면 pop 해서 변수에 저장해두고 짝이 맞을 때까지 같은 과정 반복
❗️ 숫자는 두자리 수가 될 수 있기 때문에 스택에는 'x' 만 저장해두고 숫자는 따로 숫자 스택에 저장하기
➡️ 이미 저장해둔 변수가 있다면 앞서서 pop 한 숫자가 있다는 뜻이므로 이미 저장해 둔 변수에 더해주기
4) 스택의 top 값과 짝이 맞을 경우

• 스택이 비어있을 경우: 현재까지 괄호 짝을 모두 맞춘 것이기 때문에 숫자 스택에 있는 값들을 다 더해서 최종 ans 변수에 더해주기
• 스택이 비어있지 않을 경우: 이미 저장해 둔 변수가 있다면 변수와 괄호 가중치를 곱해줘서 숫자 스택에 push 하고 괄호 스택에 'x' push

🚨 1차 trouble

일관성 없고 예외처리도 너무 많고 난잡하게 풀이해서 감당할 수가 없음,,

✏️ 최종 솔루션

1. 여는 괄호일 경우: tmp 에 해당 괄호 가중치 곱해주기 ➡️ tmp = 1 초기화
2. 닫는 괄호일 경우
   ❗️ 닫는 괄호가 등장시 정상적인 경우라면 앞 괄호가 현재 괄호를 여는 괄호임
   1) 스택의 top 이 여는 괄호가 아니거나 스택이 비었다면 예외처리
   2) 입력받은 문자열 상에서도 바로 앞 괄호가 현재 괄호를 여는 괄호였다면 가장 안쪽에 있는 괄호이므로 최종 정답에 tmp 를 더하고 현재 괄호를 열 때 tmp 에 곱했던 가중치를 초기화
   3) 나머지는 가장 안 쪽에 있는 괄호가 아닌데 이 괄호의 가중치는 가장 안쪽 괄호 닫으면서 모두 계산해줬기 때문에 현재 괄호를 열 때 tmp 에 곱했던 가중치만 초기화
3. 모든 과정을 종료했는데도 스택이 비어있지 않다면 예외처리

📌 self feedback

기존 code와 비슷하다고 생각했는데 전혀 아니었구~
괄호가 중첩되었을 때 값을 어떻게 계산할지가 관건이었음
괄호가 하나 완성되었을 때 값을 저장해두는 것이 아니라 괄호가 하나 완성될 때마다 지금까지의 가중치를 최종 답안에 한번에 더해줘야 함

✏️ 최종 code

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

int main() {
    string s;
    cin >> s;
    
    stack<char> st;
    int ans=0,tmp=1;
    
    for(int i=0;i<s.size();i++) {
        if (s[i]=='(') {    // 가중치 2 괄호 생성
            tmp*=2;
            st.push('(');
        }
        else if(s[i]=='[') {    // 가중치 3 괄호 생성
            tmp*=3;
            st.push('[');
        }
        else if(s[i]==')') {    // 가중치 2 닫는 괄호일 때
            if (st.empty() || st.top()!='(') {  // 여는 괄호 없거나 스택이 비어있으면 예외처리
                ans=0;
                break;
            }
            else if(s[i-1]=='(') {  // 바로 () 완성
                ans+=tmp;   // 괄호 열 때 이미 가중치 계산해뒀기 때문에 바로 ans에 더하기
                tmp /=2;    // 다시 tmp값 초기화
                st.pop();
            }
            else {  // 나머지는 괄호 짝 안에 다른 괄호 있었던 경우이므로 해당 괄호 열 때 곱했던 가중치 초기화
                tmp/=2;
                st.pop();
            }
        }
        else if(s[i]==']') {    // 가중치 3 닫는 괄호일 때
            if (st.empty() || st.top()!='[') {  // 여는 괄호 없거나 스택이 비어있으면 예외처리
                ans=0;
                break;
            }
            else if(s[i-1]=='[') {  // 바로 () 완성
                ans+=tmp;   // 괄호 열 때 이미 가중치 계산해뒀기 때문에 바로 ans에 더하기
                tmp /=3;    // 다시 tmp값 초기화
                st.pop();
            }
            else {  // 나머지는 괄호 짝 안에 다른 괄호 있었던 경우이므로 해당 괄호 열 때 곱했던 가중치 초기화
                tmp/=3;
                st.pop();
            }
        }
    }
    
    if (!st.empty()) ans=0;
    
    cout << ans <<'\n';
    
}