[하한문] 프로그래머스 - 수식최대화

문제는 너무 길어서 생략하겠다.

 

간략하게 설명하자면  *  +  -  이렇게 3개의 연산자에 우선순위를 주어서 가장 큰 값을 만들어 내라는 문제다.

 

처음에는 이 문제를 vector만 이용해서 풀려고 했다.

 

우선순위는 3개라서 경우가 6개 밖에 없어서 그냥 대입해도 됬지만 근사하게 dfs로 해서 우선순위를 주었고

 

 그다음 vector에 string으로 숫자와 연산자를 구별해서 넣은 다음 

 

우선 순위 놓은 순 부터 for문을 다 돌렸다.

 

연산자를 i 번째 인덱스 에서 발견했다고 했을때 i-1번째와 i+1번째의 숫자와 i번째 연산자를 삭제하고 그 자리에 다시 계산 한 값을 넣어주는 방식으로 구현해보았다.

 

iterator를 사용 할 수 밖에 없었고 구글링해서 벡터 요소 삭제 요령을 많이 참고 했으나 70점 밖에 답이 나오지 않았다.

 

따라서 결국 후위표기법을 사용하기로 한다. 대학교 자료구조강의를 들었을 때 과제 프로젝트로 계산기를 만들라고 하셨던 적이 있어서 많이 도움이 됬다. 그때는 절망적이었는데 이번에는 머리가 잘 돌아갔다. 물론 이번 문제는 괄호가 없어서 덜 어려웠다.

 

아래 코드 이다.

#include <string>
#include <vector>
#include <iostream>
#include <math.h>
#include <stack>

using namespace std;
vector<string> v ={"a","b","c"};
vector<string> cal= {"+","-","*"};
vector<string> tmp;
string q;
bool check[3];
long long MAX =0;

void divide(string str){                        // string을 숫자와 연산자 구별해서 vector에 넣었다.
    int temp =0;
    int size = str.size();
    for(int i=0; i< size; i++){
        if(str[i] == '*' || str[i] == '-'|| str[i] == '+'){
            tmp.push_back(str.substr(temp,i-temp));
            tmp.push_back(str.substr(i,1));
            temp  = i+1;
        }
    }
    tmp.push_back(str.substr(temp,size-temp));
}

int pre(string a){                   
    for(int i=0; i<3;i++){
        if(v[i] == a)
            return i;
    }    // 숫자가 작을 수록 우선순위는 크게 한다.
}


vector<string> into_post(vector<string> s){
    vector<string> answer;
    stack<string> st;
    int size = s.size();
    for(int i=0; i<size; i++){
        if(s[i] == "*" || s[i] == "+" || s[i] == "-" ){
            while(!st.empty() && pre(st.top())<= pre(s[i])) // 스택안에 있는 연산자가 우선순위가 더 때만
            {
                answer.push_back(st.top());
                st.pop();
            }
            st.push(s[i]);
        }
        else{
            answer.push_back(s[i]);
        }
    }
    while(!st.empty()){
        answer.push_back(st.top());
        st.pop();
    }
    return answer;
}

long long calculate(vector<string> s){
    stack<long long> sum_stack;
    int size = s.size();
    for(int i=0; i<size; i++){
        if(s[i] == "*"){
            long long a = sum_stack.top();
            sum_stack.pop();
            long long b = sum_stack.top();
            sum_stack.pop();
            sum_stack.push(a*b);
        }
        else if(s[i] == "+"){
            long long a = sum_stack.top();
            sum_stack.pop();
            long long b = sum_stack.top();
            sum_stack.pop();
            sum_stack.push(b+a);
        }
        else if(s[i] == "-"){
            long long a = sum_stack.top();
            sum_stack.pop();
            long long b = sum_stack.top();
            sum_stack.pop();
            sum_stack.push(b-a);
        }
        else{
            long long as = stoi(s[i]);
            sum_stack.push(as);
        }
    }
    
    return abs(sum_stack.top());
}


void dfs(int a){   // 우선 순위 주기
    if(a>=3){
        long long answer = calculate(into_post(tmp));
        if(answer > MAX){
            MAX = answer;
        }
        return;
    }
    for(int i=0;i<3;i++){
        if(check[i] == false){
            v[a] = cal[i];
            check[i] = true;
            dfs(a+1);
            check[i] =false;
        }
    }
}

long long solution(string expression) {
    long long answer = 0;
    divide(expression);
    dfs(0);
    
    return MAX;
}