programmers 수식 최대화

programmers 수식 최대화 : programmers.co.kr/learn/courses/30/lessons/67257

코딩테스트 연습 - 수식 최대화

 

2020 카카오 인턴십 문제에서 출제된 수식 최대화 입니다.

연산자의 우선순위를 강제하여 해결해야 하는데,

문자열을 다뤄야하며 이 문제에서는 범위가 커질수록 링크드리스트를 사용하는 것이

효율면에서는 좋을 것 같습니다.

 

저는 범위가 작아서 평소에 편하게 사용하는 배열만으로 문제를 해결하였습니다.

처음에 주어진 문자열을 숫자와 연산자로 구분지어준 후에

강제한 연산자 순서대로 계산해주시면 됩니다.

 

문자열에 나온 연산자가 무엇이 있는지 알 수 없기 때문에

무엇이 나왔는지 구분해주고 순서를 줘야된다고 생각할 수도 있는데,

아래 코드 중 calcluate 함수에서 처음에 for문을 0-2까지 3번 반복합니다.

3번 반복하면서 + - * 에 대한 문자열을 강제로 확인하기 때문에

solution 내부에 *-+ *+- .. 의 6가지 경우의 수를 사용한 것 처럼 해주셔도 문제를 해결하는데 문제없습니다.

 

단, 계산이 끝났으면 숫자를 담고있는 배열은 반드시 길이가 1이 되어야 계산이 완벽하게 된 것입니다.

또한 절대값 계산해주시는 것도 잊으시면 안됩니다.

코드에 주석으로 설명을 첨부하였으니 읽어보시면 될 것 같습니다.

 

#include <string>
#include <vector>
using ll = long long;
using namespace std;

ll answer = 0;

void calculate(vector<ll> number, vector<char> exp, string str){
    // 연산자 3개를 찾습니다. (i in 0~2)
    for(int i = 0; i<3; i++){
        for(int k = 0; k<exp.size(); k++){
            char ch = exp[k];
            if(ch == str[str.size()-1]){
                // erase 때문에 링크드리스트를 사용하시는 것이 효율면에서는 좋습니다.
                if(ch == '*'){
                    ll cal = number[k]*number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                else if(ch == '+'){
                    ll cal = number[k]+number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                else if(ch == '-'){
                    ll cal = number[k]-number[k+1];
                    number.erase(number.begin()+k+1);
                    number[k] = cal;
                    exp.erase(exp.begin()+k);
                }
                k--;
            }
        }
        //탐색한 연산자는 삭제해줍니다.
        str.pop_back();
    }
    
    // 계산이 끝났을 때 길이가 1이여야 완벽히 계산된 것입니다.
    if(number.size() == 1){
        answer = max(answer, abs(number[0]));
    }
    
}

long long solution(string expression) {
    
    vector<ll> number;
    vector<char> exp;
    int num = 0;
    // 숫자와 연산자를 구분해줍니다.
    for(int i = 0; i<expression.size(); i++){
        char ch = expression[i];
        if(ch >= '0' && ch <= '9') num = num*10 + (ch-'0');
        else{
            number.push_back(num);
            num = 0;
            exp.push_back(ch);
        }
    }
    // 마지막 숫자를 추가시켜줍니다.
    number.push_back(num);
    
    // 강제로 우선순위를 지정해줍니다.
    // 총 6가지의 경우의 수가 필요합니다.
    string chstring;
    chstring = "-+*";
    calculate(number, exp, chstring);
    chstring = "+-*";
    calculate(number, exp, chstring);
    chstring = "-*+";
    calculate(number, exp, chstring);
    chstring = "*-+";
    calculate(number, exp, chstring);
    chstring = "*+-";
    calculate(number, exp, chstring);
    chstring = "+*-";
    calculate(number, exp, chstring);
        
    return answer;
}