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

✅ LV.2

📌 2020 카카오 인턴십

✏️ 최종 솔루션

⭐️ 완전탐색

1. 수식을 숫자와 연산자로 분리
   ❗️ 이 문제에서는 무조건 숫자가 연산자보다 1개 많은 유의
   ❗️ set 로 연산자의 종류도 함께 파악
2. 연산자 순서 순열 구하기 ➡️ next_permutation 사용
   ❗️ 하나의 순열 완성될 때마다 해당 순열의 연산자 순서로 연산한 결과 갱신
3. 순열 순서로 연산하기
   1) 1번에서 숫자와 연산자를 분리하여 저장한 vector 는 변동이 있으면 안되기 때문에 별도의 vector 에 복사
   2) 우선순위 연산자를 돌면서 현재 연산자와 연산자 vector 의 연산자가 동일하면 계산해주고 숫자 vector 에 결과 갱신하고 연산자 vector 도 갱신
   2-1) 현재 인덱스의 숫자 값과 다음 위치 숫자를 연산한 이후 결과를 현재 인덱스의 숫자 값에 갱신
   2-2) 현재 인덱스의 연산자는 지워주고 두 개의 숫자를 지워야 하지만 연산 결과를 앞 인덱스에 저장했기 때문에 현재 인덱스의 다음 위치를 지워주기
   2-3) for 문으로 탐색하는 중에 한 자리씩 지워줬기 때문에 인덱스-- 를 해줘서 이어서 탐색할 수 있도록 함
   3) 결과, 최종 정답 하나만 vector 에 남기 때문에 이를 절대값으로 return

📌 self feedback

for 문으로 값 추가하고 지워가는 방식이 비효율적이라고 생각했지만 인덱스 관리만 잘해준다면 자료형을 많이 쓰지 않고도 사용할 수 있었음
수식 연산이라고 무조건 stack 을 사용해야 하는 것은 아님

❗️ string 에서 long long 으로 형변환할 때 stoll 사용
❗️ 순열에는 조합 방식보다는 next_permutation 이 효율적
❗️ long long 관리 잘하기

🔗 next_permutation (순열)

✏️ 최종 code

#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

vector<long long> num;
vector<char> ov;

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

long long sol(string str) {
    vector<long long> new_num=num;
    vector<char> new_ov=ov;
    
    for(int i=0;i<str.size();i++) {
        char ch=str[i];
        int idx=0;

        for(int j=0;j<new_ov.size();j++) {
            if(ch==new_ov[j]) {

                long long res=calc(ch,new_num[j],new_num[j+1]);
                new_num[j]=res;
                new_num.erase(new_num.begin()+(j+1));
                new_ov.erase(new_ov.begin()+j);
                j--;
            }
        }
    }

    
    return abs(new_num[0]);
}

long long solution(string expression) {
    long long answer = 0;

    // 연산자와 숫자 분리
    string s="";
    set<char> st;
    for(int i=0;i<expression.size();i++) {
        char ch=expression[i];
        if(ch=='+' || ch=='*' || ch=='-') {
            ov.push_back(ch);
            st.insert(ch);
            num.push_back(stoi(s));
            s="";
        }
        else {
            s+=expression[i];
        }
    }
    
    num.push_back(stoll(s));
    
    // 연산자 우선순위 정하기
    vector<char> nov(st.begin(),st.end());
    sort(nov.begin(),nov.end());
    do {
        string str="";
        for(auto it=nov.begin();it!=nov.end();it++)
            str+=*it;

        answer=max(answer,sol(str));

    } while(next_permutation(nov.begin(),nov.end()));
    
    return answer;
}