Programmers - 수식 최대화

---

title: Programmers - 수식 최대화
date: 2022-07-09
tags:

• Algorithm

---

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

문제 요약

+, -, *과 정수로만 이루어진 수식이 주어진다. 사칙연산의 우선순위를 바꾸었을 때, 수식의 절대값 중 가장 큰 값을 return한다.

문제 풀이

간단한 구현 문제이나, 개인적으로 많이 고민이 된 문제이다.
처음에는 queue를 이용하여 처리하려고 하였으나, 그럴 경우 queue 2개를 서로 바꿔가면서 사용하여야 한다.
또한 queue에 대한 포인터 처리가 제대로 되지 않았기에 이 방식을 사용하려면 또 하나의 함수를 추가하여야 하는 상황이었다.

vector, erase 방식을 사용하기로 결정하였음에도 많이 고민이 되었다.
vector를 순회하면서 우선순위에 맞는 연산 기호를 발견하면 연산, 그리고 필요 없는 원소를 삭제하는 작업의 반복이었다.
문제가 귀찮은 작업들을 요구하기에 자연스레 프로그램이 길어졌다.
성능을 챙기기에는 너무 지저분한 프로그램이고, 성능을 버리기에는 vector 접근이 너무 자주 일어났다.
문자열 형태로 주어진 수식이 100자 이내라 성능 차이가 거의 없었으나, 매우 긴 문자열과 나눗셈 같은 기호가 추가되면 성능 차이가 생긴다.
n+1개의 수와 n개의 기호로 구분, 3가지 기호만 주어진다고 가정하겠다.
최악의 경우 6가지의 우선순위 * (n+1, n, n-1)번 탐색이 이루어진다.
결국 18n번의 탐색이 이루어지며, 약 42n번의 vector 참조, 12n번의 vector erase 연산이 실행된다.
input의 크기가 크면 지저분한 프로그램이 되더라도 성능을 챙기는 것이 나을 것이다.

프로그램

#include <string>
#include <vector>
#include <algorithm>

using std :: string ;
using std :: vector ;

long long llCalc ( long long llTemp1 , long long llTemp2 , char cOperator )
{
    if ( '+' == cOperator )
        return llTemp1 + llTemp2 ;
    if ( '-' == cOperator )
        return llTemp1 - llTemp2 ;
    return llTemp1 * llTemp2 ;
}

long long llGetFormulaResult ( char cpOperator [] , vector < long long > vNum , vector < char > vOperator )
{
    long long llAnswer = 0 ;
    int iSize = vNum.size () ;



    for ( int i = 0 ; ( i < 3 ) && ( 1 < iSize ) ; ++i )
    {
        for ( int j = 0 ; j < iSize - 1 ; ++j )
        {
            if ( vOperator [ j ] == cpOperator [ i ] )
            {
                vNum [ j + 1 ] = llCalc ( vNum [ j ] , vNum [ j + 1 ] , vOperator [ j ] ) ;
                vNum.erase ( vNum.begin () + j ) ;
                vOperator.erase ( vOperator.begin () + j ) ;
                -- iSize ;
                --j ;
            }
        }
    }

    llAnswer = vNum [ 0 ] ;

    return ( llAnswer >= 0 ) ? llAnswer : llAnswer * -1 ;
}

long long solution ( string expression )
{
    long long answer = 0 ;
    vector < long long > vNum ;
    vector < char > vOperator ;
    int iLen = expression.size () ;
    int iIndex = 0 ;
    char cdrgOperator [ 6 ] [ 3 ] = { { '+' , '-' , '*' } ,
                                      { '+' , '*' , '-' } ,
                                      { '-' , '+' , '*' } ,
                                      { '-' , '*' , '+' } ,
                                      { '*' , '+' , '-' } ,
                                      { '*' , '-' , '+' } } ;



    for ( int i = 1 ; i < iLen ; ++i )
    {
        if ( ( '+' == expression [ i ] ) || ( '-' == expression [ i ] ) || ( '*' == expression [ i ] ) )
        {
            vNum.emplace_back ( std :: stoll ( expression.substr ( iIndex , i - iIndex ) ) ) ;
            vOperator.emplace_back ( expression [ i ] ) ;
            iIndex = i + 1 ;
        }
    }
    vNum.emplace_back ( std :: stoll ( expression.substr ( iIndex , iLen - iIndex) ) ) ;


    for ( int i = 0 ; i < 6 ; ++i )
    {
        answer = std :: max ( answer , llGetFormulaResult ( cdrgOperator [ i ] , vNum , vOperator ) ) ;
    }


    return answer ;
}