[프로그래머스] 수식 최대화 (C++)

문제 URL

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

프로그래머스

[문제 설명]

다음 문제는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되었을 때, 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 문제이다.

문제의 제한사항은 아래와 같다.

 

 

 

[문제 풀이]

완전탐색으로 풀어야 하는 문제로 순열을 통해 연산자로 만들 수 있는 모든 경우를 구하여 연산을 진행해 주면 된다.

1. 각 벡터에 연산자와 피연산자 담아둔다.
이때, 어떤 연산자를 사용했는지 알아야 하기 때문에 중복되지 않는 연산자를 담아두는 벡터도 필요하다.

2. 순열을 통해 연산자로 만들 수 있는 모든 경우를 구한 뒤, 순열의 연산자 순서를 연산의 우선순위 둔다. 해당 우선순위로 피연산자 벡터에 있는 숫자들 연산한다.

3. 위 과정을 연산자로 만들 수 있는 모든 순열에 대해 수행하면서 answer에 가장 큰 값을 저장한다. 

---

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

long long solution(string expression) {
    long long answer = 0;
    vector<long long> num;  // 피연산자를 담아두는 벡터
    vector<char> exp, location;  // 연산자를 담아두는 벡터
    string n = "";
    
    for(int i = 0; i < expression.size(); i++) {
        if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*') {
            num.push_back(stoi(n));
            n = "";
            if(find(exp.begin(), exp.end(), expression[i]) == exp.end())  // 존재하지 않을 때
                exp.push_back(expression[i]);  // ex) -*+
            location.push_back(expression[i]);  // ex) -*-+
        }
        else
            n += expression[i];
    }
    
    num.push_back(stoi(n));
    sort(exp.begin(), exp.end());  // * > + > - 순으로 정렬 
    
    do {
        vector<long long> tmp_num = num;
        vector<char> tmp_loc = location;
        
        for(int i = 0; i < exp.size(); i++) {
            for(int j = 0; j < tmp_loc.size(); j++) {
                if(exp[i] == tmp_loc[j]) {
                    if(tmp_loc[j] == '+')
                        tmp_num[j] = tmp_num[j] + tmp_num[j + 1];
                    else if(tmp_loc[j] == '-')
                        tmp_num[j] = tmp_num[j] - tmp_num[j + 1];
                    else if(tmp_loc[j] == '*')
                        tmp_num[j] = tmp_num[j] * tmp_num[j + 1];
                    
                    tmp_num.erase(tmp_num.begin() + j + 1);
                    tmp_loc.erase(tmp_loc.begin() + j);
                    // 모든 데이터의 index값이 하나씩 당겨지기 때문에 포인터를 한 칸 감소
                    j--;
                }
            }    
        }
        
        if(answer < abs(tmp_num[0]))
            answer = abs(tmp_num[0]);
    } while(next_permutation(exp.begin(), exp.end()));  // 순열을 통해 연산자로 만들 수 있는 모든 경우를 구함
    // next_permutation: 현재 나와 있는 순열에서 다음 순열을 구하고 true를 반환함. 다음 순열이 없다면(or 다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환
    // 1-2-3-4의 다음 순열은 1-2-4-3
    
    return answer;
}

참고: https://eunchanee.tistory.com/88

https://yabmoons.tistory.com/687