[ 프로그래머스 / stack ] 수식 최대화 (2020 카카오 인턴십)

1. 문제

---

 

코딩테스트 연습 - 수식 최대화

 

 

 

2. 소스코드

---

- 기본적인 로직은

1) +, -, x의 우선순위를 결정한다.

2) 중위 표기법에서 후위 표기법으로 바꾼다.

3) 우선 순위에 맞게 계산된 값을 정답과 비교하고, 정답보다 크다면 저장한다.

4) 모든 경우의 수에 대해 1) ~ 3)을 반복

5) 정답 출력

 

- 후위 표기법을 제대로 알고 있다면, 문제는 크게 어렵지 않다. 후위 표기법이 문제의 9할이라고 생각.

 

소스코드

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;
unordered_map<char, int> prior = { {'-', 1}, {'+', 2}, {'*', 3} };
int visited[3];
long long answer;
vector<string> que;

long long calc() {

    stack<long long> nums;
    for (int i = 0; i < que.size(); ++i) {
        if (que[i] == "*" or que[i] == "-" or que[i] == "+") {
            long long second = nums.top(); nums.pop();
            long long first = nums.top(); nums.pop();
            char oper = que[i][0];
            switch (oper) {
            case '-': nums.push(first - second); break;
            case '*': nums.push(first * second); break;
            case '+': nums.push(first + second); break;
            }
        }
        else nums.push(stoll(que[i]));
    }
    return abs(nums.top());
}

string to_postfix(string exp) {
    string temp = "";
    stack<char> oper;
    que.clear();
    for (char ch : exp) {
        if (ch != '+' and ch != '-' and ch != '*')
            temp += ch;
        else {
            que.push_back(temp); temp = "";
            while (!oper.empty() and prior[oper.top()] >= prior[ch]) {
                string chtoStr = ""; chtoStr += oper.top(); oper.pop();
                que.push_back(chtoStr);
            }
            oper.push(ch);
        }
    }
    que.push_back(temp); // 마지막 숫자
    while (!oper.empty()) {
        string temp = "";
        que.push_back(temp += oper.top());
        oper.pop();
    }
    return temp;
}

void permutation(string exp, int depth) {
    if (depth > 3) {
        to_postfix(exp);
        long long temp = calc();
        if (temp > answer) answer = temp;
        return;
    }
     
    for (int i = 0; i < 3; ++i) {
        if (!visited[i]) {
            visited[i] = 1;
            switch (i)
            {
            case 0: prior['-'] = depth;
            case 1: prior['+'] = depth;
            case 2: prior['*'] = depth;
            }
            permutation(exp, depth + 1);
            switch (i)
            {
            case 0: prior['-'] = 0;
            case 1: prior['+'] = 0;
            case 2: prior['*'] = 0;
            }
            visited[i] = 0;
        }
    }
    return;
}

long long solution(string expression) {

    permutation(expression, 1);
    return answer;
}