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

https://school.programmers.co.kr/learn/courses/30/lessons/67257#qna

프로그래머스

 

#include <string>
#include <vector>
#include <stack>
#include <list>
#include <cctype>
using namespace std;

long long cal(long long a, long long b, char op)
{
    if (op == '*')
        return a * b;
    else if (op == '+')
        return a + b;
    else
        return a - b;
}

long long solution(string expression) {
    long long answer = 0;
    list<long long> l1;
    // * , + , - 기준
    vector<vector<char>>v1(6);
    v1[0] = { '*','+','-' };
    v1[1] = { '*','-','+' };
    v1[2] = { '+','*','-' };
    v1[3] = { '+','-','*' };
    v1[4] = { '-','*','+' };
    v1[5] = { '-','+','*' };
    string n = "";
    // 원본데이터
    for (int i = 0; i < expression.length(); i++)
    {
        if (isdigit(expression[i]))
            n += expression[i];
        else
        {
            l1.push_back(stoi(n)); n = "";
            l1.push_back((int)expression[i]);
        }
    }
    l1.push_back(stoi(n));
    long long max = -1;
    for (int i = 0; i < 6; i++)
    {
        list<long long> l2 = l1;
        for (int j = 0; j < 3; j++)
        {
            int idx = 0;
            for (list<long long>::iterator iter = l2.begin(); iter != l2.end();idx++)
            {
                if ((idx%2==1) && (char)(*iter) == v1[i][j])
                {
                    auto pre = prev(iter);
                    auto ne = next(iter);
                    *pre = cal(*pre, *ne, v1[i][j]);
                    iter = l2.erase(iter); iter = l2.erase(iter);
                    iter=pre;
                }
                else
                    iter++;
            }
            
        }
        if(l2.front()<0)l2.front()*=-1;
            if (max < l2.front())
                max = l2.front();
    }
    return max;
}

주어진 수식에서 연산자의 우선순위는 마음대로 재정의할 수 있다. 이 때, 계산값의 절댓값이 가장 큰 경우를 골라 리턴해야한다. 

 

연산자 재정의의 모든 경우를 미리 지정해놓고 for문을 돌리기로 했다. 

list에 미리 값을 파싱해놓고 for문을 돌려 우선순위인 연산자부터 계산하는 것이다. 

 

vector<vector<char>>v1(6);
    v1[0] = { '*','+','-' };
    v1[1] = { '*','-','+' };
    v1[2] = { '+','*','-' };
    v1[3] = { '+','-','*' };
    v1[4] = { '-','*','+' };
    v1[5] = { '-','+','*' };

6번의 for문을 돌며 첫번째의 경우 이중 for문 j를 돌리며 0번부터 리스트를 돌며 일치하면 계산하는 식이다.

 

// 원본데이터
    for (int i = 0; i < expression.length(); i++)
    {
        if (isdigit(expression[i]))
            n += expression[i];
        else
        {
            l1.push_back(stoi(n)); n = "";
            l1.push_back((int)expression[i]);
        }
    }
    l1.push_back(stoi(n));

리스트에 수와 연산자를 파싱해서 저장하는 과정이다. 

 

for (int i = 0; i < 6; i++)
    {
        list<long long> l2 = l1;
        for (int j = 0; j < 3; j++)

다음의 이중 for문을 통해서 max값을 구한다. 

위에 미리 지정한 6가지의 연산자 재정의 경우 중 하나씩 살펴보며 j for문으로 list를 순회하며 우선순위인 값부터 계산한다.

 

int idx = 0;
            for (list<long long>::iterator iter = l2.begin(); iter != l2.end();idx++)
            {
                if ((idx%2==1) && (char)(*iter) == v1[i][j])
                {
                    auto pre = prev(iter);
                    auto ne = next(iter);
                    *pre = cal(*pre, *ne, v1[i][j]);
                    iter = l2.erase(iter); iter = l2.erase(iter);
                    iter=pre;
                }
                else
                    iter++;
            }

idx는 홀수번째에 연산자가 있을 것이기 때문에 이를 위한 인덱스이다. 

아니면 정수인지 연산자인지 구분이 힘들기 때문이다. 

 

list를 순회하기 위해서 iterator를 이용한다.

prev, next함수를 이용해 연산자 기준 앞,뒤 값을 받아온다. 이는 연산에 필요한 두 수이다. a * b 일 때, a,b

 

long long cal(long long a, long long b, char op)
{
    if (op == '*')
        return a * b;
    else if (op == '+')
        return a + b;
    else
        return a - b;
}

cal 함수는 다음과 같다.

 

계산 후에 pre 즉 a * b 일 때 a 위치에 계산값을 저장하고 * 와 b는 제거한다. 

list.erase(iter) 를 하면 iter가 가리키던 다음반복자를 리턴한다. 

따라서 iter = list.erase(iter)를 두번하여 * 와 b를 삭제한다. 

 

마지막에 iter 에 pre값을 주어 다시 연결한다. 

 

이 때는 iter를 증가시키지 않는다. 

 

a->*->b 상황에서 

a->b,  a 가 되고 a를 가리키라고 iter에 pre를 대입한다. 

 

if(l2.front()<0)l2.front()*=-1;
            if (max < l2.front())
                max = l2.front();

j for문이 완료되면 즉 계산을 끝내면 리스트에는 한개의 원소밖에 남지 않는다. 

절댓값이 max보다 크면 변경한다.