Programming프로그래머스자료구조스택

프로그래머스 - 수식 최대화 (Cpp)

,

https://programmers.co.kr/learn/courses/30/lessons/67257

문제 해설

경우의 수 문제이다. 모든 경우의 연산자 우선순위를 만들어 해당 연산자 우선순위를 이용해 연산을 진행하면 된다.

중위표기식으로 나타난 식을 후위 표기식으로 바꿔서 문제를 해결 했다.

경우의 수 만들기

만들 수 있는 모든 연산자 우선순위를 만들어줘야 한다. DFS를 이용해 모든 경우의 수를 만들어 줬다.

void makeAllCase(int depth) {
    if (depth == 3) {
        allCase.push_back(cntCase);
    }

    for (int i = 0; i < 3; i++) {
        int cntOper = operation[i];

        if (check[i] == false) {
            check[i] = true;
            cntCase[depth] = cntOper;
            makeAllCase(depth + 1);
            check[i] = false;
        }
    }
}

연산자 우선순위를 가반으로 한 연산

  1. 가장 높은 우선순위의 연산자가 들어왔을 때

    • Stack을 확인해 같은 먼저 들어온 같은 우선순위의 연산자가 있는지 확인한다.
    • 같은 우선순위의 연산자가 Stack에 있는 경우 pop 해서 해당 연산을 진행한 후 지금 들어온 연산자를 push한다.
    • 없는 경우에는 Stack에 push 한다.

  2. 두번째 우선 순위가 연산자가 들어온 경우

    • Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다.
    • Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다.

  3. 세번째 우선 순위의 연산자가 들어온 경우

    • Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다.
    • Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다.
// 첫번째 우선순위의 연산자가 들어온 경우
if (cntChar == cnt_priority[0]) {
    opernand.push(stol(value));
    value = "";

    while (!operation.empty() && operation.top() == cnt_priority[0]) {
        long long value1 = opernand.top();
        opernand.pop();
        long long value2 = opernand.top();
        opernand.pop();
        char oper = operation.top();
        operation.pop();

        long long result = calValue1Value2(value1, value2, oper);
        opernand.push(result);
    }

    operation.push(cntChar);
}

// 두번째 우선순위의 연산자가 들어온 경우
if (cntChar == cnt_priority[1]) {
    opernand.push(stol(value));
    value = "";

    while (!operation.empty() && operation.top() != cnt_priority[2]) {
        long long value1 = opernand.top();
        opernand.pop();
        long long value2 = opernand.top();
        opernand.pop();
        char oper = operation.top();
        operation.pop();

        long long result = calValue1Value2(value1, value2, oper);
        opernand.push(result);
    }

    operation.push(cntChar);
}

// 세번째 우선순위의 연산자가 들어온 경우
if (cntChar == cnt_priority[2]) {
    opernand.push(stol(value));
    value = "";

    while (!operation.empty()) {
        long long value1 = opernand.top();
        opernand.pop();
        long long value2 = opernand.top();
        opernand.pop();
        char oper = operation.top();
        operation.pop();

        long long result = calValue1Value2(value1, value2, oper);
        opernand.push(result);
    }

    operation.push(cntChar);
}

Stack을 이용한 소스 코드

#include <bits/stdc++.h>
using namespace std;

char operation[3] = {'*', '+', '-'};
bool check[3];
vector<char> cntCase(3);
vector<vector<char>> allCase;

void makeAllCase(int depth) {
    if (depth == 3) {
        allCase.push_back(cntCase);
    }

    for (int i = 0; i < 3; i++) {
        int cntOper = operation[i];

        if (check[i] == false) {
            check[i] = true;
            cntCase[depth] = cntOper;
            makeAllCase(depth + 1);
            check[i] = false;
        }
    }
}

long long calValue1Value2(long long value1, long long value2, char oper) {
    long long result = 0;

    if (oper == '*') {
        result = value2 * value1;
    } else if (oper == '+') {
        result = value2 + value1;
    } else {
        result = value2 - value1;
    }
    return result;
}

long long solveExpression(string expression) {
    long long maxValue = 0;

    for (vector<char> cnt_priority : allCase) {
        stack<long long> opernand;
        stack<char> operation;

        string value = "";
        for (int i = 0; i < expression.size(); i++) {
            char cntChar = expression[i];

            if ('0' <= cntChar && cntChar <= '9') {
                value += cntChar;
            }

            if (cntChar == cnt_priority[0]) {
                opernand.push(stol(value));
                value = "";

                while (!operation.empty() && operation.top() == cnt_priority[0]) {
                    long long value1 = opernand.top();
                    opernand.pop();
                    long long value2 = opernand.top();
                    opernand.pop();
                    char oper = operation.top();
                    operation.pop();

                    long long result = calValue1Value2(value1, value2, oper);
                    opernand.push(result);
                }

                operation.push(cntChar);
            }

            if (cntChar == cnt_priority[1]) {
                opernand.push(stol(value));
                value = "";

                while (!operation.empty() && operation.top() != cnt_priority[2]) {
                    long long value1 = opernand.top();
                    opernand.pop();
                    long long value2 = opernand.top();
                    opernand.pop();
                    char oper = operation.top();
                    operation.pop();

                    long long result = calValue1Value2(value1, value2, oper);
                    opernand.push(result);
                }

                operation.push(cntChar);
            }

            if (cntChar == cnt_priority[2]) {
                opernand.push(stol(value));
                value = "";

                while (!operation.empty()) {
                    long long value1 = opernand.top();
                    opernand.pop();
                    long long value2 = opernand.top();
                    opernand.pop();
                    char oper = operation.top();
                    operation.pop();

                    long long result = calValue1Value2(value1, value2, oper);
                    opernand.push(result);
                }

                operation.push(cntChar);
            }
        }
        opernand.push(stol(value));

        while (!operation.empty()) {
            long long value1 = opernand.top();
            opernand.pop();
            long long value2 = opernand.top();
            opernand.pop();
            char oper = operation.top();
            operation.pop();

            long long result = calValue1Value2(value1, value2, oper);
            opernand.push(abs(result));
        }

        if (maxValue < opernand.top()) {
            maxValue = opernand.top();
        }
    }
    return maxValue;
}

long long solution(string expression) {
    long long answer = 0;
    makeAllCase(0);
    answer = solveExpression(expression);
    return answer;
}

dq를 이용한 문제 해결

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

char operation[3] = {'+', '-', '*'};
bool check[3];
vector<char> op(3);
vector<vector<char>> operations;
deque<long long> dq_opernand;
deque<char> dq_operator;
ll max_value = 0;

void nPr(int depth) {
    if (3 == depth) {
        vector<char> v(op);
        operations.push_back(op);
        return;
    }

    for (int i = 0; i < 3; i++) {
        if (check[i] == true)
            continue;
        op[depth] = operation[i];

        check[i] = true;
        nPr(depth + 1);
        check[i] = false;
    }
}

void divideOperaion(string expression) {
    string s;
    for (int i = 0; i < expression.size(); i++) {
        if ('0' <= expression[i] && expression[i] <= '9') {
            s += expression[i];
        } else {
            dq_opernand.push_back(stol(s));
            dq_operator.push_back(expression[i]);
            s = "";
        }
    }
    dq_opernand.push_back(stol(s));
}

long long operValue(ll a, ll b, char op) {
    if (op == '+') {
        return a + b;
    } else if (op == '-') {
        return a - b;
    } else {
        return a * b;
    }
}

void operate(string expression) {
    deque<ll> temp_opernand;
    deque<char> temp_operator;

    for (auto o : operations) {
        deque<ll> copy_opernand(dq_opernand);
        deque<char> copy_operator(dq_operator);

        for (int i = 0; i < 3; i++) {
            char cnt_operation = o[i];

            while (!copy_operator.empty()) {
                if (copy_operator.front() == cnt_operation) {
                    ll value1 = copy_opernand.front();
                    copy_opernand.pop_front();

                    ll value2 = copy_opernand.front();
                    copy_opernand.pop_front();

                    char oper = copy_operator.front();
                    copy_operator.pop_front();

                    ll result = operValue(value1, value2, oper);

                    copy_opernand.push_front(result);
                } else {
                    temp_opernand.push_back(copy_opernand.front());
                    temp_operator.push_back(copy_operator.front());

                    copy_opernand.pop_front();
                    copy_operator.pop_front();
                }
            }

            while (!copy_opernand.empty()) {
                temp_opernand.push_back(copy_opernand.front());
                copy_opernand.pop_front();
            }

            while (!temp_operator.empty()) {
                copy_operator.push_back(temp_operator.front());
                temp_operator.pop_front();
            }

            while (!temp_opernand.empty()) {
                copy_opernand.push_back(temp_opernand.front());
                temp_opernand.pop_front();
            }
        }
        max_value = max(max_value, abs(copy_opernand.front()));
    }
}

long long solution(string expression) {
    long long answer;
    nPr(0);
    divideOperaion(expression);
    operate(expression);
    answer = max_value;
    return answer;
}
Share