프로그래머스 - 수식 최대화(67257)

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

프로그래머스

---

문제 설명

오직 숫자와 +, -, * 연산자로 이루어진 문자열 수식이 다음과 같이 제공됩니다. "100-200*300-500+20" 
이 문자열 수식에서 연산자 우선순위를 정의하여 해당 수식에 결과의 절대값이 가장 큰 값이 무엇인지 구해야합니다.

예시로 "100-200*300-500+20"  수식은 * > + > - 로 연산자 우선순위를 정한다면 -60,420으로 절대값 60420으로 가장 큰 결과 값을 가집니다.

다음 주어진 수식들을 가장 절대값이 큰 결과값이 나오도록 연산자 우선순위를 정하고 결과값을 구하시오.

---

아이디어

1. 먼저 주어진 문자열을 숫자와 연산자로 분리합니다. ["100", "-", "200" ... "+", "20"]

2. 연산자가 3개이니 3! = 6으로 6가지 연산자 조합이 나오니 6가지 연산자 조합을 일일히 돌려줍니다.

3. 나온 결과를 가지고 비교해서 최대 결과값을 구합니다.

---

코드

#include <string>
#include <vector>
#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

void separate(list<string> &e, string s)
{
    string tmp = "";
    for(auto c : s)
    {
        if(c == '-' || c == '*' || c == '+'){
            e.push_back(tmp);
            tmp = "";
            tmp += c;
            e.push_back(tmp);
            tmp = "";
        }
        else{
            tmp += c;
        }
    }
    e.push_back(tmp);
}

long long caculate(list<string> e, string priority){
    for(auto p : priority){
        long long tmp;
        list<string>::iterator iter = e.begin();
        
        while(true){
            if(iter == e.end()) break;
            
            string sp(1, p);
            if(*iter == sp){
                // ++, -- 였는데 prev, next로 변경하고 통과
                list<string>::iterator before = prev(iter);
                list<string>::iterator after = next(iter);
                if(p == '*') tmp = stoll(*before) * stoll(*after);
                if(p == '+') tmp = stoll(*before) + stoll(*after);
                if(p == '-') tmp = stoll(*before) - stoll(*after);
                
                *(before) = to_string(tmp);
                iter = e.erase(iter);
                iter = e.erase(iter);
            }
            else{
                iter++;
            }
        }
    }
    return abs(stoll(e.front()));
}

long long solution(string expression) {
    long long answer = 0;
    list<string> e;
    separate(e, expression);
    vector<string> operation = {"*+-", "*-+", "+*-", "+-*", "-*+", "-+*"};
    
    for(auto s : operation){
        caculate(e, s);
        answer = max(answer, caculate(e, s));
    }
    
    return answer;
}

---

추가 내용

○ 리스트 사용 : 분리된 문자열을 리스트로 쓴 이유는 연산자 우선순위를 따라 연산된 노드들을 삭제할 일이 많아 생성/삭제에 용이한 리스트를 쓰는게 좋다 생각했습니다.

○ caculate함수에서 iterator 자체를 조작하다가 문제가 많이 생겼는데, prev(), next()를 사용해서 해결됐습니다.