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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/67257

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

---

문제 풀이는 다음과 같다.

1. 기본 연산을 배열로 저장한다 (*,+,-)

이때 주의해야할 점이, Next Permutation을 사용하려면 해당 배열(혹은 백터)은 이미 정렬이 완료되어있어야 한다.

때문에 배열을 입력한 다음 정렬을 한 번 해주거나, 아니면 입력할때부터 아스키 코드값이 작은 순서로 입력을 해줘야한다.

이 점을 간과하면 아무리 로직이 맞아도 테스트 케이스 1번에서부터 실패할 수 있다.

2. 문제로 주어지는 숫자와 연산자의 값을 따로 벡터에 저장해준다. 

3. do-while, next permutation을 활용하여 조합되는 순열대로 저장된 연산자의 갯수만큼 계산을 진행한다.

이때 숫자와 연산자의 값은 새로운 백터에 값을 저장하여 활용한다.

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long go(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 solution(string expression) {
    long long answer = 0;
    string temp = "";
    vector<char> basic_operation = {'*','+','-'};
    vector<char> cal;
    vector<long long> num;
    for(auto i:expression){
        if(i=='*'||i=='-'||i=='+') {
            cal.push_back(i);
            num.push_back(stoll(temp)); // string to long long
            temp="";
        }
        else temp += i;
    }
    num.push_back(stoll(temp)); // 마지막 숫자
    do{
        vector<long long> temp_num = num;
        vector<char> temp_cal = cal;
        for(int i=0; i<3; i++){
            for(int j=0; j<temp_cal.size(); j++){
                if(basic_operation[i]==temp_cal[j]){
                    temp_num[j] = go(temp_num[j],temp_num[j+1],temp_cal[j]);
                    temp_num.erase(temp_num.begin()+j+1);// 숫자를 지운다
                    temp_cal.erase(temp_cal.begin()+j);// 계산식을 지운다
                    j--; // 주의! 1개 지웠으니 한 번 뒤로 되돌아가야한다
                }
            }
        }
        answer = max(abs(temp_num[0]),answer);
    }while(next_permutation(basic_operation.begin(), basic_operation.end()));
    return answer;
}

정확성 테스트

테스트 1 〉	통과 (0.01ms, 3.95MB)
테스트 2 〉	통과 (0.01ms, 3.97MB)
테스트 3 〉	통과 (0.02ms, 3.95MB)
테스트 4 〉	통과 (0.02ms, 3.98MB)
테스트 5 〉	통과 (0.02ms, 3.95MB)
테스트 6 〉	통과 (0.02ms, 3.94MB)
테스트 7 〉	통과 (0.02ms, 3.97MB)
테스트 8 〉	통과 (0.02ms, 3.84MB)
테스트 9 〉	통과 (0.02ms, 3.93MB)
테스트 10 〉	통과 (0.02ms, 3.95MB)
테스트 11 〉	통과 (0.02ms, 3.97MB)
테스트 12 〉	통과 (0.02ms, 3.83MB)
테스트 13 〉	통과 (0.02ms, 3.97MB)
테스트 14 〉	통과 (0.02ms, 3.95MB)
테스트 15 〉	통과 (0.02ms, 3.96MB)
테스트 16 〉	통과 (0.01ms, 3.95MB)
테스트 17 〉	통과 (0.02ms, 3.96MB)
테스트 18 〉	통과 (0.01ms, 3.95MB)
테스트 19 〉	통과 (0.01ms, 3.97MB)
테스트 20 〉	통과 (0.01ms, 3.84MB)
테스트 21 〉	통과 (0.02ms, 3.95MB)
테스트 22 〉	통과 (0.02ms, 3.8MB)
테스트 23 〉	통과 (0.01ms, 3.96MB)
테스트 24 〉	통과 (0.02ms, 3.97MB)
테스트 25 〉	통과 (0.02ms, 3.96MB)
테스트 26 〉	통과 (0.02ms, 3.94MB)
테스트 27 〉	통과 (0.02ms, 3.96MB)
테스트 28 〉	통과 (0.02ms, 3.9MB)
테스트 29 〉	통과 (0.02ms, 3.96MB)
테스트 30 〉	통과 (0.02ms, 3.96MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0