본문 바로가기

알고리즘 · 코딩

[프로그래머스] 수식 최대화

[2020 카카오 인턴십] 수식 최대화

 

문제 링크

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

 

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

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과

programmers.co.kr


C++ 풀이

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

long long calculate(long long a, long long b, char opr) {
    if (opr == '+')
        return a + b;
    else if (opr == '-')
        return a - b;
    else if (opr == '*')
        return a * b;
}

long long solution(string expression) {
    long long max_num = 0;
    vector<char>operator_list = { '*', '+', '-' };
    vector <long long> nums;
    vector <char> operators;
    string num = "";
    for (int i = 0; i < expression.length(); i++) { //수와 연산자를 나눠서 저장
        if (expression[i] == '*' || expression[i] == '+' || expression[i] == '-') {
            nums.push_back(atoi(num.c_str()));
            num = "";
            operators.push_back(expression[i]);
        }
        else {
            num += expression[i];
        }
    }
    nums.push_back(atoi(num.c_str()));
    do { //연산자 우선순위에 맞춰 계산
        vector <long long>  temp_nums = nums;
        vector <char> temp_operators = operators;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < temp_operators.size(); j++) {
                if (temp_operators[j] == operator_list[i]) {
                    temp_nums[j] = calculate(temp_nums[j], temp_nums[j + 1], operator_list[i]);
                    temp_nums.erase(temp_nums.begin() + j + 1);
                    temp_operators.erase(temp_operators.begin() + j);
                    j--;
                }
            }
        }
        if (abs(temp_nums.front()) > max_num)
            max_num = abs(temp_nums.front());
    } while (next_permutation(operator_list.begin(), operator_list.end()));
    return max_num;
}

수와 연산자를 위한 두 개의 벡터를 두고, 연산자 우선순위 리스트를 next_permutation으로 구하여 풀었다.

 

 

 

반응형

'알고리즘 · 코딩' 카테고리의 다른 글

[SWEA 10200] 구독자 전쟁  (0) 2021.01.08
[SWEA 10505] 소득 불균형  (0) 2021.01.07
[SWEA 1289] 원재의 메모리 복구하기  (0) 2021.01.04
[프로그래머스] 보석 쇼핑  (0) 2021.01.02
[SWEA 1256] K번째 접미어  (0) 2021.01.01