2020 Kakao internship 67257 - 수식 최대화(파싱, 완전탐색, 배열) c++ 풀이

 

- 연산자 혹은 괄호 문제만 나오면 스택으로 풀 생각만 했는데, 그렇게 안 풀어도 되는 문제였다. 

- 모든 연산자 우선순위 조합에 대해서 최대값을 구하는데 vector erase연산으로 계산된 피연산자를 벡터에서 제거해나가는 방식으로 풀었다.

- 연산자랑 피연산자를 따로 분리했는데 strtok을 사용했다. strtok은 여러개의 delimiter에 대해서 분리가 되도록 짤 수 있어서 stringstream과 함께 자주 사용한다. 개인적으로 분리자 단위가 공백문자면 stringstream을 주로 사용하고 여러개이면 strtok을 자주 사용한다. 

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

vector<char> order{'+', '-', '*'}; // 연산자 순열용
vector<long long> nums, cpy_nums; // 피연산자, 원본 저장용
vector<char> op, cpy_op; // 연산자

long long calc() {
    for(int i = 0; i < 3; ++i) { // 연산자 순서대로
        for(int j = 0; j < op.size(); ++j) {
            if(op[j] == order[i]) {
                if(op[j] == '+') {
                    nums[j] += nums[j+1];
                } else if(op[j] == '-') {
                    nums[j] -= nums[j+1];
                } else {
                    nums[j] *= nums[j+1];
                }
                
                nums.erase(nums.begin() + j + 1); 
                op.erase(op.begin() + j);
                --j;
            }
        }
    }
    
    return abs(nums[0]);
}

long long solution(string expression) {
    long long ans = 0;
    
    char exp[100];
    strcpy(exp, expression.c_str());
    
    char* p = strtok(exp, "+-*");
    while(p != NULL) {
        nums.push_back(stoll(p));
        p = strtok(NULL, "+-*");
    }
    
    for(char ch: expression) {
        if(ch == '+' || ch == '-' || ch == '*')
            op.push_back(ch);
    }
    
    cpy_nums = nums;
    cpy_op = op;
    
    sort(order.begin(), order.end());
    do {
        nums = cpy_nums;
        op = cpy_op;
        ans = max(ans, calc());
    } while(next_permutation(order.begin(), order.end()));
    
    return ans;
}

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

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