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

수식 최대화

코딩테스트 연습 - 수식 최대화 | 프로그래머스 (programmers.co.kr)

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

조건

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 $2^{63}-1$ 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

 

 

풀이

해당 문제는 연산자의 우선순위가 주어질 때 수식(expression)을 계산하는 것이 핵심이다.

 

수식을 계산하는 코드를 작성한 후에, 연산자의 우선순위를 변경해주면 된다.

여기서 연산자의 우선순위를 바꾼다 하더라도 경우의 수는 6가지이다.

따라서 모든 경우를 시도해봐도 시간문제가 없을 것이다.

 

풀이 방법을 정리하면 다음과 같다.

 

1. 연산자의 우선순위를 지정한다.
2. 지정된 우선순위에 따라 수식을 계산한다.
3. 수식의 계산 값의 절댓값이 이전에 계산한 것보다 더 높으면 이를 기록한다.
4. 연산자의 우선순위를 다른 것으로 바꿔보고, 더 바꿀 수 없을 때 종료한다.

 

next_permutation이 다음 순열을 계산할 수 있으므로 {1, 2, 3}에 대해서 순열을 돌려서 우선순위를 결정하도록 한다.

 

첫 번째 숫자부터 각각 더하기, 빼기, 곱하기의 우선순위를 가리킨다고 하면, 1순위부터 3순위까지 차례대로 연산을 실행하도록 한다.

예를 들어 (숫자 1) + (숫자 2)가 주어져 있고 그다음에 곱하기 연산자(*)가 주어져 있다고 하자.

그러면 더하기 연산자와 곱하기 연산자의 우선순위를 비교해서, 더하기 연산자의 우선순위가 더 높거나 같으면 지금 주어진 수를 계산하도록 한다.

만약 다음 연산자가 주어지지 않았거나 곱하기 연산자가 우선순위가 더 높으면 현재 수를 계산하지 않는다.

 

수식 계산은 스택 계산기를 활용했다.

스택에 ExpNode로 숫자 또는 연산자가 들어가도록 해서, 숫자, 연산자, 숫자, 연산자, 숫자 순서로 들어가게 된다.

이전 연산자와 이후 연산자를 따로 저장해놔서, 이전 연산자와 이후 연산자의 상태를 보고 현재 스택에서 값을 빼서 계산할 것인지 아닌지를 판단하도록 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <cctype>
#include <cstdlib>

using namespace std;

int curIndex = 0; // 문자열 내 읽고 있는 인덱스
// 연산자 또는 수식 타입. 숫자 또는 연산자를 가리킨다.
enum ExpType
{
    NUMBER, PLUS, MINUS, MULT, NONE
};

// 수식 노드
struct ExpNode
{
    long long number;
    ExpType type;
};

// 다음 수를 획득한다.
long long GetNextNumber(string expression)
{
    long long number = 0;
    do
    {
        number = number * 10 + (expression[curIndex] - '0');
        curIndex++;
    } while (curIndex < expression.length() && isdigit(expression[curIndex]));
    return number;
}

// 다음 연산자를 획득한다.
ExpType GetNextOperator(string expression)
{
    ExpType type;
    if (curIndex >= expression.length())
        return NONE;
    else if (expression[curIndex] == '+')
        type = PLUS;
    else if (expression[curIndex] == '-')
        type = MINUS;
    else
        type = MULT;
    curIndex++;
    return type;
}

// 수식 계산
long long CalcExp(long long left, long long right, ExpType op)
{
    switch(op)
    {
        case PLUS:
            left += right;
            break;
        case MINUS:
            left -= right;
            break;
        case MULT:
            left *= right;
            break;
    }
    return left;
}

long long solution(string expression) {
    long long answer = 0;
    ExpType lastOperator = NONE;
    ExpType nextOperator = NONE;
    // 연산자 우선순위. 첫 인덱스는 숫자, 마지막 인덱스는 연산자가 없을 때의 우선순위를 가리킨다.
    int priority[5] = { 0, 1, 2, 3, 10 }; 

    // 모든 연산자 케이스별로 반복한다.
    do
    {
        curIndex = 0;
        stack<ExpNode> expStack;
        
        // 숫자 노드 하나 받는다.
        long long number = GetNextNumber(expression);
        // 연산자가 있으면 받는다.
        nextOperator = GetNextOperator(expression);
        
        expStack.push({number, NUMBER});
        if (nextOperator != NONE)
            expStack.push({0, nextOperator});

        // 다음 연산자가 없을 때까지 수식을 입력받는다.
        while (nextOperator != NONE && curIndex < expression.length())
        {
            // 다음 숫자와 연산자를 받는다.
            number = GetNextNumber(expression);

            lastOperator = nextOperator;
            nextOperator = GetNextOperator(expression);
            
            expStack.push({number, NUMBER}); // 수를 스택에 푸쉬함
            
            // 수식을 연산함
            while (priority[lastOperator] <= priority[nextOperator] &&
                expStack.size() >= 3) // 다음 연산자의 우선순위가 높거나 stack에 1개 남을 때까지 연산
            {
                long long left, right;
                right = expStack.top().number;
                expStack.pop(); expStack.pop();
                left = expStack.top().number;
                expStack.pop();
                
                long long result = CalcExp(left, right, lastOperator);
                
                // 결과를 push하기 전에 다음 연산자를 획득한다.
                lastOperator = expStack.empty() ? NONE : expStack.top().type;
                
                expStack.push({result, NUMBER});
            }
            
            if (nextOperator != NONE)
                expStack.push({0, nextOperator});
        }
        
        answer = max(answer, abs(expStack.top().number)); // 스택의 결과 값과 비교
    } 
    while (std::next_permutation(priority + PLUS, priority + MULT + 1));
    
    return answer;
}

// 테스트용
int main()
{
    std::string s;
    std::cin >> s;
    std::cout << solution(s) <<'\\n';

    return 0;
}

 

코드를 너무 장황하게 써서 문제가 많았다.

다음번에는 좀 더 깔끔하게 써야지.