수식 최대화

유승선 ·2022년 10월 28일
0

프로그래머스

목록 보기
32/48

카카오에서 정말로 흔하게 내는 완전탐색류의 문제다. 이미 블로그로 커버한줄 알았는데 안해서 놀랐다. 백준 문제를 풀다가 문득 생각이 나서 풀게됐는데 처음에 구상을 생각하면서 더하기 뺼샘 구현을 생각하느라 시간을 많이 썼던거 같다. 그래도 여전히 재미있고 좋아하는 문제로 남았다. 이 문제는 expression 스트링 안에서 적절하게 숫자를 파싱하고 수식을 골라내는 걸로 시작해야한다. 그리고 걸러낸 수식을 바탕으로 dfs 를 돌리면서 Permutation을 만들어야한다. 왜냐면은 완전탐색 문제이기 때문에 모든 가능성을 전부 찾아봐야 하기때문.

우선 순위로 되어있는 수식어를 기준으로 계산을 계속해야하는데 이때 잘 생각해보면 계산을 하는 벡터가 따로 있어야하고 원래 순서를 지키는 벡터가 따로 있어야하기 때문에 Copy 라는 이름의 벡터를 계산중에 만들어주었다. 추가적으로 dfs를 할때도 수식어가 반복되는게 아니고 유니크한 permuation의 수식어가 있어야하기 때문에 set를 활용해주었다.

계산 하는 방법은 개인마다 차이가 있겠지만 내가 구상했던 부분은 전부 구현했고 erase() 메서드를 써가지고 계속 조절을 해주었다.

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;

vector<long long> numVec; 
vector<char> expressVec; 
vector<char> opVec; 

void dfs(int cnt, vector<bool>& visited, vector<vector<char>>& comb, vector<char>& tmp){
    if(cnt == expressVec.size()){
        comb.push_back(tmp);
        return; 
    }
    for(int i = 0; i < expressVec.size(); i++){
        if(!visited[i]){
            visited[i] = true; 
            tmp.push_back(expressVec[i]); 
            dfs(cnt + 1, visited, comb, tmp); 
            visited[i] = false; 
            tmp.pop_back(); 
        }
    }
}

long long solution(string expression) {
    long long answer = 0;
    string nums = ""; 
    set<char> charSet; 
    for(char& c : expression){
        if(isdigit(c)) nums += c; 
        else{
            charSet.insert(c); 
            opVec.push_back(c); 
            numVec.push_back(stoi(nums)); 
            nums = ""; 
        }
    }
    numVec.push_back(stoi(nums)); 
    for(auto& c : charSet) expressVec.push_back(c); 
    vector<bool> visited(expressVec.size(),false); 
    vector<vector<char>> comb; 
    vector<char> tmp; 
    sort(expressVec.begin(),expressVec.end()); 
    dfs(0,visited,comb,tmp); 
    for(vector<char>& vv : comb){
        vector<long long> copyNum = numVec;
        vector<char> copyOp = opVec; 
        for(int i = 0; i < vv.size(); i++){
            for(int j = 0 ; j < copyOp.size(); j++){
                if(vv[i] == copyOp[j]){
                    if(vv[i] == '*'){
                        copyNum[j+1] = copyNum[j] * copyNum[j+1]; 
                    }
                    if(vv[i] == '+'){
                        copyNum[j+1] = copyNum[j] + copyNum[j+1]; 
                    }
                    if(vv[i] == '-'){
                        copyNum[j+1] = copyNum[j] - copyNum[j+1]; 
                    }
                    copyOp.erase(copyOp.begin() + j);
                    copyNum.erase(copyNum.begin() + j); 
                    j--; 
                }
            }
        }
        answer = max(answer,(long long)abs(copyNum[0])); 
    }
    return answer;
}
profile
성장하는 사람

0개의 댓글