[프로그래머스] 수식 최대화 - 완전 탐색

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 

 

수식 최대화(링크)

풀이

연산자는 *, +, - 세 개이므로 가능한 우선 순위는 총 6가지이다. 주어지는 문자열은 길이 100 이하로 모두 검사하기 쉬운 분량이므로 가능한 우선 순위를 모두 확인한다. 나는 "*+-" 문자열 변수를 선언한 뒤 next_permutation() 으로 가능한 순서를 모두 나열하게 했다.

 

처음엔 주어진 문자열 그대로 우선순위에 따라 계산하고 결과를 다시 문자열에 붙여 넣는 방식으로 하나하나 계산하려 했다. 과정이 명시적이고 문자열 출력을 통해 진행 상황을 확인하기 쉽지만 문자열을 고쳐 넣는 과정이 포함되어서 불필요하게 코드가 길어진다.

 

또한, 중간에 음의 부호를 가지는 숫자를 삽입할 때 부호가 아닌 연산자와 구분하기 위한 추가적인 코드가 필요하다.

 

훨씬 간편한 방법은 두 개의 vector 를 사용하는 것이다. 연산자와 숫자를 분리하여 저장한 뒤 연산자 vector 에서 우선 순위의 연산자를 찾으면 숫자 vector 에서 같은 인덱스의 숫자와 그 다음 위치의 숫자를 피연산자로 하여 연산한다. 연산 후 해당 숫자와 연산자를 vector.erase() 하기만 하면 다음 연산도 같은 방식으로 진행할 수 있다.

복기

C++의 string 은 vector 와 같이 [ ] 연산자로는 access out of range 에 대해 에러를 반환하지 않는다. vector와 마찬가지로 string.at() 메소드를 사용하면 안전하게 사용할 수 있다.

 

반환 타입이 long long 이므로 중간 계산할 때도 타입을 맞추는 것이 안전하다. 

 

처음에는 주어지는 수식에 포함된 연산자들에 대해서만 우선 순위를 만들었는데, 세 가지 연산자를 사용하므로 기껏해야 여섯 가지의 우선순위가 있다. 이런 경우는 단순히 상수 배열 등으로 우선 순위를 하드 코딩하는 것이 더 효율적이라고 생각한다.

 

문제에서 주어진 2^63 - 1 을 보고 long long 타입을 생각해 내야 한다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

long long calculate(long long ln, long long rn, char oper) {
    long long ret;

    if (oper == '*') ret = ln * rn;
    else if (oper == '+') ret = ln + rn;
    else if (oper == '-') ret= ln - rn;

    return ret;
}

long long solveExpression(vector<long long> numbers, vector<char> operators, string priority) {
    for (int priorityIdx = 0; priorityIdx < priority.length(); ++priorityIdx) {
        // Search for the prior operator.
        for (int operIdx = 0; operIdx < operators.size(); ++operIdx) {
            if (operators.at(operIdx) == priority.at(priorityIdx)) {
                // Calculate the sub expression and extract the operands and operator.
                long long ans = calculate(numbers.at(operIdx), numbers.at(operIdx + 1), operators.at(operIdx));
                numbers.erase(numbers.begin() + operIdx);
                numbers.erase(numbers.begin() + operIdx);
                operators.erase(operators.begin() + operIdx);

                numbers.insert(numbers.begin() + operIdx, ans);
                operIdx -= 1;
            }
        }
    }
    return numbers.at(0);
}

long long solution(string expression) {
    long long answer = 0;
    vector<char> operators;
    vector<long long> numbers;
    string number = "";
    string priority = "*+-";

    // Seperate numbers and operators in each vector.
    for (int i = 0; i < expression.length(); ++i) {
        // expression[i] is a number.
        if ('0' <= expression.at(i) && expression.at(i) <= '9') {
            number += expression.at(i);
        } else { 
            // expression[i] is an operator.
            numbers.push_back(stoi(number));
            operators.push_back(expression.at(i));
            number = "";
        }
    }
    // Add the last number of the expression.
    numbers.push_back(stoi(number));

    // Solve the expression with all the possible priorities.
    do {
        // Choose the maximum result.
        answer = max(answer, abs(solveExpression(numbers, operators, priority)));
    } while (next_permutation(priority.begin(), priority.end()));

    return answer;
}

int main(int argc, char* argv[]) {
    cout << solution(argv[1]) << endl;
    return 0;
}