[프로그래머스] 수식 최대화 / stack

문제

 

풀이

#include <string>
#include <vector>
#include <sstream>
#include <stack>


using namespace std;

long long  calc(long long a, long long b, char c){
    long long n = 0;
    switch(c){
        case '-':
            n = a-b;
            break;
        case '+':
            n = a+b;
            break;
        case '*':
            n = a*b;
            break;
    }
    return n;
}

long long solution(string expression) {
    vector<vector <char>> priors = {{'-', '+', '*'},{'-', '*', '+'},
                                    {'+', '-', '*'}, {'+', '*', '-'},
                                    {'*', '-', '+'}, {'*', '+', '-'}};
    
    long long max_val = 0;
    long long val = 0;
    long long  num;
    char sign;
    
    stack<long long > num_s;
    stack<char> sign_s;
    vector<long long > num_v;
    vector<char> sign_v;
    
    vector<long long > v1; // 숫자 
    vector<char> v2; // 부호
                
    //각각의 배열에 넣기
    string ex = expression;
    stringstream ss(ex);
    while(ss){ 
        if(ss >> num) {
            v1.push_back(num);
        }
        if(ss >> sign){
            v2.push_back(sign);
        }  
    }
        
    
    for(auto prior : priors){
        
        num_v = v1;
        sign_v = v2;
        
        while(num_v.size() > 1){
            for(int i=0; i<prior.size(); i++){
            //계산
                num_s.push(num_v[0]);
                for(int k=0; k<sign_v.size(); k++){
                    num_s.push(num_v[k+1]);
                    sign_s.push(sign_v[k]);
                    if(sign_s.top() == prior[i]){
                        long long n2 = num_s.top();
                        num_s.pop();
                        long long n1 = num_s.top();
                        num_s.pop();
                        char ci = sign_s.top();
                        sign_s.pop();
                        num_s.push(calc(n1,n2,ci));  
                    }
                }
                //스택에 있는 자료들을 배열로 옮기기
                num_v.clear(); // 초기화
                sign_v.clear();
                while(!num_s.empty()){
                    num_v.insert(num_v.begin(),num_s.top());
                    num_s.pop();
                }
                
                while(!sign_s.empty()){
                    sign_v.insert(sign_v.begin(),sign_s.top());
                    sign_s.pop();
                }
            }
        }    
        val = labs(num_v[0]);
        if(max_val < val) max_val = val;
        num_v.clear();
    }
    return max_val;
}

순서대로 계산을 해야 했기 때문에 stack 자료구조가 적절하다고 생각했다.

 

1. 숫자와 부호 따로따로 추출하여 벡터에 넣는다.

2. 우선순위인 부호가 나올 경우 연산 후 결과를 숫자 스택에 넣는다.

3. 숫자 스택의 크기가 1일 때까지(결괏값) 반복한다.

 

더 간단하게 짜고싶었는데 생각보다 코드가 복잡해졌다.

 

 

---

 

 

다른 사람 풀이

#include <string>
#include <vector>
#include <cmath>

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    vector<long long> nums;
    vector<char> op;

    int idx = 0;
    for(int i=0;i<expression.size();i++){
        char ch = expression[i];
        if(ch == '*' | ch == '+' | ch == '-'){
            op.push_back(ch);
            nums.push_back(stoi(expression.substr(idx,i-idx)));
            idx = i+1;
        }else if(i == expression.size()-1){
            nums.push_back(stoi(expression.substr(idx,i-idx+1)));
        }
    }

    string prior[6] = {
        "*+-", "*-+",
        "+*-", "+-*", 
        "-*+", "-+*",
    };

    for(int i=0;i<6;i++){
        vector<long long> temp_nums = nums;
        vector<char> temp_op = op;
        string pr = prior[i];
        for(int j=0;j<3;j++){
            for(int k=0;k<temp_op.size();k++){
                if(pr[j] == temp_op[k]){
                    if(pr[j] == '*'){
                        temp_nums[k] = temp_nums[k]*temp_nums[k+1];
                        temp_nums.erase(temp_nums.begin()+k+1);
                    }else if(pr[j] == '+'){
                        temp_nums[k] = temp_nums[k]+temp_nums[k+1];
                        temp_nums.erase(temp_nums.begin()+k+1);
                    }else if(pr[j] == '-'){
                        temp_nums[k] = temp_nums[k]-temp_nums[k+1];
                        temp_nums.erase(temp_nums.begin()+k+1);
                    }
                    temp_op.erase(temp_op.begin()+k--);
                }
            }
        }
        answer = max(answer, abs(temp_nums[0]));
    }

    return answer;
}

stringstream를 쓰지 않고 sbustr을 사용해서 문자를 추출했다.

문자열에서 원하는 데이터를 추출해야 할 때 stringstream를 이용해야 한다고 생각했는데, 새로운 방법을 알게 되었다.

 

벡터만을 이용해서 풀 수 있는 문제였는데, 과정을 너무 복잡하게 생각한 것 같다!