[PG/C++] 프로그래머스 Lv2 - 수식 최대화

😎 문제 설명

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

프로그래머스

문제는 단순했다. 문자열로 주어진 수식을 계산하되, 연산자의 우선순위를 임의로 지정해 최댓값을 구하도록 하는 문제였다. 이때 수식을 계산한 값은 절댓값으로 비교하고, 최종 결괏값이 2의 63승 미만으로 나오기 때문에 long long 타입을 적극적으로 활용해야하는 문제였다.

💗 해결 과정

수식에는 최대 3개의 연산자가 주어져있고, 이 연산자의 우선순위를 정해서 Brute-force 방식으로 각 우선순위마다 답을 구해 최댓값을 구하는 방식으로 풀었다.

 

(1) 모든 연산자의 우선순위를 테스트하는 방법 : algorithm 헤더의 next_permutation 함수를 이용해 모든 연산자의 우선순위를 테스트하였다. next_permutation을 이용하기 전에, 수식에 사용된 부호를 priorities에 따로 저장한 후 sort하였다.

 

(2) 우선순위에 따라 수식을 계산하는 방법 : calculate 함수에서 구현하였다. 만약 +, -, * 순서대로 연산을 해야한다면 수식을 모두 탐색하며 + 연산을 먼저 처리하고, 그 다음 - 처리, 마지막으로 *을 처리한 후 남은 하나의 숫자로 result를 반환하였다. 이 과정을 예제 입력 1을 예시로 하여 그림으로 나타내면 아래와 같다.

수식을 한 번 탐색하며 연산할 때, 연산하고자 하는 연산자가 연속으로 나오는 경우를 처리하기 위해 nn의 마지막 원소에 접근해 compute 함수의 인자로 넣어주었다. 앞에서 nn에 저장된 값이 바로 다음 연산자에서 사용되는 경우가 있기 때문이다.

 

(3) 최댓값을 계산하는 방법 : do while 구문에서 cmath 헤더의 abs 함수를 이용해 calculate 함수 반환값의 절댓값을 구하고, 최댓값을 계산하는 방식으로 구현하였다.

⭐ 해결 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

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

long long calculate(vector<long long> n, string s, string priorities){
    long long result = 0; 

    for(char c : priorities){ // 연산자 우선순위 순서대로 계산
        int j = 0; // 연산자(s)의 인덱스
        vector<long long> nn; 
        string ss;
        nn.push_back(n[0]);

        while(true){
            if(j == s.length()) break;

            if(s[j] == c) {  
                long long last = nn.back(); nn.pop_back(); 
                nn.push_back(compute(last, n[j + 1], s[j]));
                j++;
            } else {
                nn.push_back(n[j + 1]); 
                ss.push_back(s[j]); 
                j++; 
            }
        }
        result = nn.back(); 

        n = nn; 
        s = ss;
    }
    return result; 
}

long long solution(string expression) {
    long long answer = 0;

    vector<long long> n; string s; 
    string number;

    string priorities;
    for(char c : expression){
        if(c == '+' || c == '-' || c =='*') {
            s += c;
            if(priorities.find(c) == string::npos) // 최초로 발견된 부호라면
                priorities.push_back(c); 
            n.push_back(stoi(number)); 
            number.clear(); 
        }
        else 
            number += c; 
    }
    n.push_back(stoi(number)); 

    sort(priorities.begin(), priorities.end()); 
    do{
        long long cand = calculate(n, s, priorities); 
        if(answer < abs(cand)) answer = abs(cand); 
    } while(next_permutation(priorities.begin(), priorities.end()));

    return answer;
}

💪 고찰

문자열로 주어진 수식에서 숫자만 뽑기 위해서는 string 헤더의 stoi함수를 사용하면 된다. 

#include <string> 

int main(){
	string expression; 
    
    string currentNumber; 
    vector<int> numbers; // 숫자를 저장할 벡터
    for(char c : expression){
    	if(std::isdigit(c)){
        	currentNumber.push_back(c); 
        } else {
        	numbers.push_back(std::stoi(currentNumber)); 
            currentNumber.clear();
    	}
   }
}