C++ / 프로그래머스 / 수식 최대화

문제

 

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

프로그래머스

문제풀이

 

사칙연산 중에서 나눗셈을 제외한 +, -, * 을 가지고 모든 경우의 수를 확인해서 절댓값이 가장 큰 값을 구하는 문제이다.

사칙연산과는 달리 우선순위가 같은 연산자는 없다.

 

next_permutation을 이용하여 모든 경우의 수를 탐색하도록 했다.

벡터를 이용해서 idx의 값과 idx+1의 값을 연산을 하고, 해당 값을 idx에 저장, idx+1는 erase를 하여 숫자를 합하였다.

 

void init(string expression) {
    string num("");
    for (int idx = 0; idx < expression.size(); ++idx) {
        if (idx + 1 == expression.size()) {
            num += expression[idx];
            init_nums.push_back(stoi(num));
        }
        if (isdigit(expression[idx]) > 0) num += expression[idx];
        else {
            init_nums.push_back(stoi(num));
            init_oprs.push_back(expression[idx]);
            num.clear();
            use.insert(expression[idx]);
        }
    }
}

입력을 받고 입력을 숫자, 연산자로 나누는 함수이다.

init_nums는 숫자들을 나열한 벡터, init_oprs은 연산자들을 나열한 벡터, 마지막으로 use는 사용하는 연산자를 체크하는 

set이다.

 

input 크기만큼 반복하면서 숫자와 문자를 파싱하는 코드이다.

isdigit을 이용하여 해당 문자가 숫자인지 문자인지를 판별한다.

해당 인덱스가 연산자라면 num을 int형으로 변환하여 숫자 벡터에, 연산자는 연산자 벡터에 저장한다.

 

void search() {
    vector<char>order(use.begin(), use.end());

    do {
        vector<ll>nums = init_nums;
        vector<char>oprs = init_oprs;

        for (int cnt = 0; cnt < order.size(); ++cnt) {
            for (int idx = 0; idx < oprs.size();) {
                if (order[cnt] == oprs[idx]) {
                    if (oprs[idx] == '+') nums[idx] = nums[idx] + nums[idx + 1];
                    else if (oprs[idx] == '-') nums[idx] = nums[idx] - nums[idx + 1];
                    else if (oprs[idx] == '*') nums[idx] = nums[idx] * nums[idx + 1];

                    nums.erase(nums.begin() + idx + 1);
                    oprs.erase(oprs.begin() + idx);
                }
                else ++idx;
            }
        }
        ll num = abs(nums[0]);

        answer = max(answer, num);

    } while (next_permutation(order.begin(), order.end()));
}

char형 벡터인 order은 use에 저장된 연산자들을 복사해서 사용한다.

next_permutation함수를 통해 모든 경우의 수를 탐색한다.

반복할 때마다 init_nums와 init_oprs의 값을 삭제할 것이기 때문에 따로 nums와 oprs을 선언하여 반복마다 복사하여 사용한다.

 

만약 현재 인덱스의 연산자와 지금 연산자 벡터의 연산자가 같다면 nums[idx]에 nums[idx] (연산) nums[idx+1] 값을 저장하고 nums [idx+1]을 삭제한다.

연산자 벡터의 연산자도 삭제한다.

 

이런 식으로 계속 반복하면서 answer의 값을 최댓값으로 경신한다.

 

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;

vector<ll>init_nums;
vector<char>init_oprs;
set<char>use;

ll answer;

void search() {
    vector<char>order(use.begin(), use.end());

    do {
        vector<ll>nums = init_nums;
        vector<char>oprs = init_oprs;

        for (int cnt = 0; cnt < order.size(); ++cnt) {
            for (int idx = 0; idx < oprs.size();) {
                if (order[cnt] == oprs[idx]) {
                    if (oprs[idx] == '+') nums[idx] = nums[idx] + nums[idx + 1];
                    else if (oprs[idx] == '-') nums[idx] = nums[idx] - nums[idx + 1];
                    else if (oprs[idx] == '*') nums[idx] = nums[idx] * nums[idx + 1];

                    nums.erase(nums.begin() + idx + 1);
                    oprs.erase(oprs.begin() + idx);
                }
                else ++idx;
            }
        }
        ll num = abs(nums[0]);

        answer = max(answer, num);

    } while (next_permutation(order.begin(), order.end()));
}

void init(string expression) {
    string num("");
    for (int idx = 0; idx < expression.size(); ++idx) {
        if (idx + 1 == expression.size()) {
            num += expression[idx];
            init_nums.push_back(stoi(num));
        }
        if (isdigit(expression[idx]) > 0) num += expression[idx];
        else {
            init_nums.push_back(stoi(num));
            init_oprs.push_back(expression[idx]);
            num.clear();
            use.insert(expression[idx]);
        }
    }
}

ll solution(string expression) {
    init_nums = vector<ll>();
    init_oprs = vector<char>();
    use = set<char>();

    init(expression);
    search();

    return answer;
}