• Home
  • About
    • Jiwon Jeong photo

      Jiwon Jeong

      끊임없이 배우며 성장하는 엔지니어

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • All Categories
  • Projects

Stack 뼈대 문제

10 May 2021

Reading time ~1 minute

괄호의 값(백준) - 뼈대문제

  • 힌트 : 분배법칙 이용
    • 2x(2+3x3)은 (2x2) + (2x3x3)과 같다.
//2504 괄호의 값
#include <iostream>
#include <string>
#include <stack>
 
using namespace std;
 
string str;
stack<char> s;
 
int main(void) {
    cin >> str;
 
    int answer = 0, temp = 1;
    for(int i = 0; i < str.length(); i++) {
        if(str[i] == '(') {
            temp *= 2;
            s.push('(');
        }
        else if(str[i] == '[') {
            temp *= 3;
            s.push('[');
        }
        else if(str[i] == ')') {
            if(s.empty() || s.top() != '(') {   //올바르지 못한 괄호열
                answer = 0;
                break;
            }
            if(str[i-1] == '(') {
                answer += temp;
                temp /= 2;
                s.pop();
            }
            else {
                temp /= 2;
                s.pop();
            }
        }
        else if(str[i] == ']') {
            if(s.empty() || s.top() != '[') {   //올바르지 못한 괄호열
                answer = 0;
                break;
            }
            if(str[i-1] == '[') {
                answer += temp;
                temp /= 3;
                s.pop();
            }
            else {
                temp /= 3;
                s.pop();
            }
        }
    }
 
    if(!s.empty()) answer = 0;  //올바르지 못한 괄호열
 
    cout << answer << "\n";
 
    return 0;
}



Algorithm Share Tweet +1