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

이 문제를 푸는데엔 꽤나 오랜 시간이 걸렸다.

중위 표기법을 후위 표기법으로 바꾸는 법 부터 알아야 했다.

주먹구구식으로 먼저 문제를 풀었고, 그것 자체도 굉장히 오랜 시간이 소요되었다.

#include <string>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <stack>
#include <cstring>
#include <iostream>

using namespace std;

bool visit[3];
set<char> op;
map<char, int> m;

long long maxValue = 0;

vector<string> split(string input, char delimiter) {
    vector<string> answer;
    stringstream ss(input);
    string temp;
 
    while (getline(ss, temp, delimiter)) {
        answer.push_back(temp);
    }
 
    return answer;
}



void calculate(string expression) {
    
    stringstream ss(expression);
    
    string newS = "";
    stack<char> opStk;
    
    int num;
    char ch;
    
    ss >> num;
    newS += to_string(num);
    newS += " ";
    
    while(ss >> ch >> num) {
        
        while(!opStk.empty() && m[opStk.top()] >= m[ch]) {
            newS += opStk.top();
            newS += " ";
            opStk.pop();
        }
        opStk.push(ch);
        
        
        newS += to_string(num);
        newS += " ";
                

    }
    
    while(!opStk.empty()) {
        newS += opStk.top();
        newS += " ";
        opStk.pop();
    }
    
    // newS에 후위표시로 식 완성
    // 잘 됨
//    cout << newS << "\n";
    
    
    vector<string> result = split(newS, ' ');
    stack<long long> stk;

    for(int i = 0; i < result.size(); i++) {

        if(result[i] != "*" && result[i] != "-" && result[i] != "+") {
            stk.push(stoi(result[i]));
        } else {

            long long num2 = stk.top();
            stk.pop();
            long long num1 = stk.top();
            stk.pop();

            long long resultValue = 0;

            if(result[i] == "*") {
                resultValue = num1 * num2;
            } else if(result[i] == "-") {
                resultValue = num1 - num2;
            } else if(result[i] == "+") {
                resultValue = num1 + num2;
            }
            stk.push(resultValue);
        }
    }

//    cout << stk.top() << "\n";
    if(maxValue <= abs(stk.top())) {
        maxValue = abs(stk.top());
    }



    
}

void dfs(string expression, int priority) {
    
    if(priority >= op.size() + 1) {
        
        // 계산 시작
        calculate(expression);
        return;
    }
    
    
    
    for(auto i = op.begin(); i != op.end(); i++) {
        
        if(!visit[distance(op.begin(), i)]) {
            
            visit[distance(op.begin(), i)] = true;
            
            m[*i] = priority;
            dfs(expression, priority + 1);
            
            visit[distance(op.begin(), i)] = false;
        }
        
    }
    
}

long long solution(string expression) {
    long long answer = 0;
        
    for(auto c : expression) {
        if('0' <= c && c <= '9') ;
        else op.insert(c);
    }
    
    dfs(expression, 1);
    
    
    return maxValue;
}

 

그리고 나서 다른 분들의 풀이를 알아보다가 next_permutation() 이라는 함수를 새로 알게 되었고, 이를 활용하게 되었다.

#include <string>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <stack>
#include <algorithm>

using namespace std;

set<char> op;
map<char, int> m;

long long maxValue = 0;

vector<string> split(string input, char delimiter) {
    vector<string> answer;
    stringstream ss(input);
    string temp;
 
    while (getline(ss, temp, delimiter)) {
        answer.push_back(temp);
    }
 
    return answer;
}



void calculate(string expression) {
    
    stringstream ss(expression);
    
    string newS = "";
    stack<char> opStk;
    
    int num;
    char ch;
    
    ss >> num;
    newS += to_string(num);
    newS += " ";
    
    while(ss >> ch >> num) {
        
        while(!opStk.empty() && m[opStk.top()] >= m[ch]) {
            newS += opStk.top();
            newS += " ";
            opStk.pop();
        }
        opStk.push(ch);
        
        
        newS += to_string(num);
        newS += " ";
                

    }
    
    while(!opStk.empty()) {
        newS += opStk.top();
        newS += " ";
        opStk.pop();
    }
    
    // newS에 후위표시로 식 완성
    // 잘 됨
//    cout << newS << "\n";
    
    
    vector<string> result = split(newS, ' ');
    stack<long long> stk;

    for(int i = 0; i < result.size(); i++) {

        if(result[i] != "*" && result[i] != "-" && result[i] != "+") {
            stk.push(stoi(result[i]));
        } else {

            long long num2 = stk.top();
            stk.pop();
            long long num1 = stk.top();
            stk.pop();

            long long resultValue = 0;

            if(result[i] == "*") {
                resultValue = num1 * num2;
            } else if(result[i] == "-") {
                resultValue = num1 - num2;
            } else if(result[i] == "+") {
                resultValue = num1 + num2;
            }
            stk.push(resultValue);
        }
    }

//    cout << stk.top() << "\n";
    if(maxValue <= abs(stk.top())) {
        maxValue = abs(stk.top());
    }



    
}

long long solution(string expression) {
    long long answer = 0;
        
    for(auto c : expression) {
        if('0' <= c && c <= '9') ;
        else op.insert(c);
    }
    
    vector<int> v;
    for(int i = 1; i <= op.size(); i++) {
        v.push_back(i);
    }
    
    do {
        
        for(auto iter = op.begin(); iter != op.end(); iter++) {
            
            m[*iter] = v[distance(op.begin(), iter)]; // index를 구해줌
        }
        
        calculate(expression);
        
        
    } while(next_permutation(v.begin(), v.end()));
    

    
    return maxValue;
}

next_permutation을 사용하니까 확실히 코드의 양이 상당히 줄었다.

 

 

그래도 여전히 코드가 길었기에,, 다른 분들이 푼 풀이를 좀 참고하고자 찾아봤다.

근데 전위/후위 이런걸 고려해서 Stack으로 풀려고 한다기보다는, 그냥 반복문으로 푼 풀이가 많았고,

코드도 굉장히 간단한 편에 속했다.

 

 

숫자 따로, 연산자 따로 vector에 따로 담아준 다음에

next_permutation을 이용해서 마찬가지로 모든 경우의 수에 맞게 해주는데,

만약 + - * 순으로 하게 된다면

먼저 + 를 찾아서 모두 계산해주고, 그다음 - 를 찾아서 모두 계산해주고, 그 다음 *를 찾아서 모두 계산해주는 방식이다.

 

---

이 문제를 통해서 알게된 점

 

1. 문자열에 정수값을 넣어주고 싶을 때 

 

string s = "";

int num = 100;

 

s += num 하면 d가 들어감.

to_string(num) 해야함.

 

 

2. stringstream 주의사항

int main() {
    
//    cout << solution("100-200*300-500+20");
    
    stringstream ss("100+100");
    
    int num;
    char ch;
    
    ss >> num >> ch;
    
    cout << num << " " << ch << " ";
    
    ss >> num >> ch;
    
    cout << num << " " << ch << " ";
}

100 + 100 찍히고 말아야 한다고 생각하는데

왜 100 + 100 + 가 찍히는지 모르겠다.

 

stringstream에 대한 이해가 아직도 부족하다.

 

 

int main() {
    
//    cout << solution("100-200*300-500+20");
    
    stringstream ss("100");
    
    int num;
    char ch;
        
    ss >> num >> num >> num;
    
    cout << num << "\n";
    
}

아무리 찍어도 num은 100이 고정된다.

while(ss >> num) 이런 식이 있길래, num에 null같은 값이 담기는 줄 알았는데,,

이건 ss >> num에 리턴문이 따로 있나보다.

 

3. next_permuation 함수

next_permutation(v.begin(), v.end())를 이용해서 순열을 구현할 수 있다.

 

 

4. set에서 index가 필요할 때

distance(op.begin(), iter); 를 이용하면 된다.

 

5. set에서는 split 함수가 없다.

C++에서는 split 함수가 없기 때문에 정의해서 만들어줘야 했다.