[프로그래머스] 수식 최대화 (문제 설명, 해결 과정, 코드 전문, c++)

• 문제 설명
• 해결 과정
• 코드 전문

 

문제 설명

 

 

본 문제는 프로그래머스의 수식 최대화 문제입니다.

 

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

 

 

 

 

 

해결 과정

 

이번 문제는 주워진 식에서 *, +, - 세 연산자의 우선순위를 바꿔가며 얻을 수 있는 가장 큰 수를 구하는 문제입니다.

*, +, - 로 얻을 수 있는 모든 경우는 6개이며 저는 순열을 이용하여 모든 경우에 접근하였습니다.

우선 주워진 식이 문자열의 형태라 숫자와 연산자를 따로 분리해야합니다. 이후 각 순열마다 우선순위에 맞춰

연산을 진행합니다. 우선순위가 가장 빠른 연산자부터 식에서 찾아 그 앞 숫자와 뒷 숫자를 연산해 스택에 집어 넣습니다. 이러한 과정을 가장 효율적으로 수행하는 자료구조는 stack이기에 채용하였습니다. 이후 해당 순열에서 얻을 수 있었던

가장 큰 수를 배열에 담으며 모든 경우에서 수행한 뒤에 그 배열에서 가장 큰 값을 반환합니다.

 

 

 

 

코드 전문

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <stack>

using namespace std;

void parser_op(string s, vector<string> &res)
{
    string temp_str;
    for (auto ch : s)
    {
        if (isdigit(ch))
            temp_str += ch;
        else
        {
            res.emplace_back(temp_str);
            temp_str = ch;
            res.emplace_back(temp_str);
            temp_str.clear();
        }
    }
    if (!temp_str.empty())
        res.emplace_back(temp_str);
}

long long solution(string expression) {
    vector<string> e;
    vector<string> t_e;
    long long answer = 0;
    stack<string> stk;
    vector<unsigned long long> result;
    vector<string> op = { "+", "-", "*" };
    sort(op.begin(), op.end());

    parser_op(expression, e);

    string t;
    string t2;
    do
    {
        t_e = e;
        for (auto o : op)
        {

            for (int i = 0; i < t_e.size(); i++)
            {
                if (!stk.empty() && t_e[i] == o)
                {
                    t = stk.top();
                    t2 = t_e[i + 1];
                    stk.pop();
                    if (o == "*")
                    {
                        stk.push(to_string(stoll(t) * stoll(t2)));
                        i++;
                    }
                    else if (o == "+")
                    {
                        stk.push(to_string(stoll(t) + stoll(t2)));
                        i++;
                    }
                    else if (o == "-")
                    {
                        stk.push(to_string(stoll(t) - stoll(t2)));
                        i++;
                    }
                }
                else stk.push(t_e[i]);
            }
            t = stk.top();
            t_e.clear();
            while (!stk.empty())
            {
                t_e.emplace_back(stk.top());
                stk.pop();
            }
            reverse(t_e.begin(), t_e.end());
            
        }
        
        result.emplace_back(abs(stoll(t)));
        while (!stk.empty()) stk.pop();

    } while (next_permutation(op.begin(), op.end()));

    answer = *max_element(result.begin(), result.end());

    return answer;
}

 

 

 

 

느낀 점 (잡설 99% , 배운점 1%(많은 편))

 

지금까지 여러번 범했던 실수인 string parameter에 char 형태를 넣는 행위를 이번 문제를 통해서

인식하고 줄여나가기 시작했습니다. 왜 내가 쓰는 STL은 오류투성이야 절망했는데. C++에서 STL만큼 훌륭한게 없네요. 반복자도 그렇고 여러 모던 C++의 요소들이 안정적인 코딩을 위해 돕는 것 같습니다.

 

그리고 안 풀리는 점이 몇 가지있다면 막상 만들다 보니 필요한 변수나 자료구조들이 생기면 그에 마땅한 네이밍이

떠오르지 않아 임시적인 이름을 두고 진행해버립니다. 이름을 지을 수 너무 추상적이거나 너무 길게 적어

딱 이거다 하는 이름이 잘 안 떠오르네요. 책장에 있는 클린 코드라도 읽어봐야겠습니다.

 

 

 

 

 

 

 

 

긴 글 읽어주셔서 감사합니다. 

부족한 점이 있다면 부디 알려주시면 감사하겠습니다.