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

https://school.programmers.co.kr/learn/courses/30/lessons/67257?language=cpp 

프로그래머스

전체 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> v;
vector<string> copy_v;
bool visit[4];
int pri[4]; // + - *
long long ans = 0;
void solve(int idx, int cnt)
{
    if (cnt == 3)
    {
        copy_v = v;
        while (copy_v.size() != 1)
        {
            int pos;
            int maxPri = 0;
            for (int i = 0; i < copy_v.size(); i++)
            {
                if (copy_v[i] == "+" && maxPri < pri[1])
                {
                    pos = i;
                    maxPri = pri[1];
                }
                else if (copy_v[i] == "-" && maxPri < pri[2])
                {
                    pos = i;
                    maxPri = pri[2];
                }
                else if (copy_v[i] == "*" && maxPri < pri[3])
                {
                    pos = i;
                    maxPri = pri[3];
                }

            }
            long long res = 0; // 이것 int가 아닌 long long으로
            if (copy_v[pos] == "+")
                res = stoll(copy_v[pos - 1]) + stoll(copy_v[pos + 1]);
            else if (copy_v[pos] == "-")
                res = stoll(copy_v[pos - 1]) - stoll(copy_v[pos + 1]);
            else
                res = stoll(copy_v[pos - 1]) * stoll(copy_v[pos + 1]);
            copy_v.erase(copy_v.begin() + (pos - 1), copy_v.begin() + (pos + 2));
            copy_v.insert(copy_v.begin() + (pos - 1), to_string(res));
        }
        if (stoll(copy_v[0]) < 0)
            copy_v[0].erase(copy_v[0].begin());
        
        ans = max(ans, stoll(copy_v[0]));
        return;
    }

    for (int i = 1; i < 4; i++)
    {
        if (visit[i] == false)
        {
            visit[i] = true;
            pri[idx] = i;
            solve(idx + 1, cnt + 1);
            visit[i] = false;
        }
    }



}


long long solution(string expression) {
    long long answer = 0;
    string str;
    for (int i = 0; i < expression.length(); i++)
    {
        if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*')
        {
            v.push_back(str);
            str = "";
            string s;
            s += expression[i];
            v.push_back(s);
        }
        else
            str += expression[i];
    }
    v.push_back(str); // 마지막 수를 안넣었다..
    solve(1, 0);
    answer=ans;
    return answer;
}

 

 

조금 지저분하게 코드가 작성되었다...

그냥 간단히 각 연산자에 대해 우선순위를 매겨

그 우선순위를 적용하여 식을 풀어 최대가 되는 값을 찾으면 된다.

 

 

string str;
    for (int i = 0; i < expression.length(); i++)
    {
        if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*')
        {
            v.push_back(str);
            str = "";
            string s;
            s += expression[i];
            v.push_back(s);
        }
        else
            str += expression[i];
    }
    v.push_back(str); // 마지막 수를 안넣었다..

주어진 입력을 수와 연산자로 분리해 저장한다.

 

void solve(int idx, int cnt)

idx는 현재 인덱스(우선순위를 매길 인덱스) -> pri배열에 pri[1]은 +의 우선순의 pri[2]는 -의 우선순위 pri[3]은 *의 우선순위

cnt는 몇개의 연산자에 대해 우선순위를 매겼는가?

 

if (cnt == 3)
    {
        copy_v = v;
        while (copy_v.size() != 1)
        {
            int pos;
            int maxPri = 0;
            for (int i = 0; i < copy_v.size(); i++)
            {
                if (copy_v[i] == "+" && maxPri < pri[1])
                {
                    pos = i;
                    maxPri = pri[1];
                }
                else if (copy_v[i] == "-" && maxPri < pri[2])
                {
                    pos = i;
                    maxPri = pri[2];
                }
                else if (copy_v[i] == "*" && maxPri < pri[3])
                {
                    pos = i;
                    maxPri = pri[3];
                }

            }
            long long res = 0; // 이것 int가 아닌 long long으로
            if (copy_v[pos] == "+")
                res = stoll(copy_v[pos - 1]) + stoll(copy_v[pos + 1]);
            else if (copy_v[pos] == "-")
                res = stoll(copy_v[pos - 1]) - stoll(copy_v[pos + 1]);
            else
                res = stoll(copy_v[pos - 1]) * stoll(copy_v[pos + 1]);
            copy_v.erase(copy_v.begin() + (pos - 1), copy_v.begin() + (pos + 2));
            copy_v.insert(copy_v.begin() + (pos - 1), to_string(res));
        }
        if (stoll(copy_v[0]) < 0)
            copy_v[0].erase(copy_v[0].begin());
        
        ans = max(ans, stoll(copy_v[0]));
        return;
    }

3개의 연산자에 대해 우선순위가 매겨졌다면

우선순위에 따라 식을 계산한다.

이때 우선순위가 제일 큰 연산자의 위치를 pos로 기록한다.

그리고 그 연산자의 종류에 맞춰 pos-1과 pos+1의 수를 연산하여 그 자리에 삽입한다.

이는 수 1개만 남을때까지 반복한다.

만약 마지막 1개의 수가 음수일 경우 부호를 떼준다.

 

for (int i = 1; i < 4; i++)
    {
        if (visit[i] == false)
        {
            visit[i] = true;
            pri[idx] = i;
            solve(idx + 1, cnt + 1);
            visit[i] = false;
        }
    }

우선순위를 매기는 코드이다.

 

 

풀면서 주의할 부분

v.push_back(to_string('@'));
v.push_back("@");

v.push_back("1");
v.push_back(to_string('1'));

서로 다른게 들어간다...

"@"은 벡터에 @가 그대로 들어가지만

"to_string('@')"는 10진수 64로 들어간다...

 

벡터가 비었을때 아래의 코드에서 에러가 나더라...

vv.insert(vv.begin()+1-1, 5); // 이러면 iterator 에러가 뜬다..
vv.insert(vv.begin()+(1-1), 5); // 묶어주면 또 안뜸...

 

연산 순서 때문에 그런 것 같은데 다음부터 따로 묶어줘야겠다.

 

long long res = 0; // 이것 int가 아닌 long long으로

중간중간 연산 결과를 저장하는 변수를 int로 해버릴 뻔했다.

아마 int로 하면 중간에 오버플로우가 일어날 것이다.