[programmers] Lv.2 수식 최대화(c++)

처음엔 정규표현식을 사용해 숫자 연산자 숫자를 찾아 계산하고싶었다. (너무 어렵게 생각한것같음)

예시는 통과했지만, 대부분의 tc는 통과하지 못했다.

아직 이유를 파악하지 못했다...

#include <string>
#include <vector>
#include <regex>

using namespace std;

string add(string str){    
    smatch match;
    
    while(regex_search(str, match, regex("(\\d+[+](-)?\\d+)|(^(-)\\d+[+](-)?\\d+)"))){
        long long a, b;
        sscanf(match.str().c_str(), "%lld+%lld", &a, &b);
        str.replace(str.find(match.str()), match.str().length(), to_string(a+b));
    }
    return str;
}

string subtract(string str){
    smatch match;
    
    while(regex_search(str, match, regex("(\\d+[-](-)?\\d+)|(^(-)?\\d+[-](-)?\\d+)"))){
        long long a, b;
        sscanf(match.str().c_str(), "%lld-%lld", &a, &b);
        str.replace(str.find(match.str()), match.str().length(), to_string(a-b));
    }
    return str;
}

string multiply(string str){
    smatch match;
    
    while(regex_search(str, match, regex("(\\d+[*](-)?\\d+)|(^(-)?\\d+[*](-)?\\d+)"))){
        long long a, b;
        sscanf(match.str().c_str(), "%lld*%lld", &a, &b);
        str.replace(str.find(match.str()), match.str().length(), to_string(a*b));
    }
    return str;
}

long long solution(string expression) {
    long long answer = 0;
    long long res = 0;
    
    // * + -
    answer = abs(stoll(subtract(add(multiply(expression)))));
    // * - +
    res = abs(stoll(multiply(add(subtract(expression)))));
    if(answer < res) answer = res;
    // + - *
    res = abs(stoll(multiply(subtract(add(expression)))));
    if(answer < res) answer = res;
    // - + *
    res = abs(stoll(multiply(add(subtract(expression)))));
    if(answer < res) answer = res;    
    // + * -
    res = abs(stoll(subtract(multiply(add(expression)))));
    if(answer < res) answer = res;
    // - * +
    res = abs(stoll(add(multiply(subtract(expression)))));
    if(answer < res) answer = res;
    return answer;
}

 

#include <string>
#include <vector>
#include <regex>
#include <map>

using namespace std;


vector<string> add(vector<string> str){
    auto iter = find(str.begin(), str.end(), "+");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a+b));
        iter = find(str.begin(), str.end(), "+");
    }
    return str;
}

vector<string> subtract(vector<string> str){
    auto iter = find(str.begin(), str.end(), "-");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a-b));
        iter = find(str.begin(), str.end(), "-");
    }
    return str;
}

vector<string> multiply(vector<string> str){
    auto iter = find(str.begin(), str.end(), "*");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a*b));
        iter = find(str.begin(), str.end(), "*");
    }
    return str;
}

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

    // split
    vector<string> split_expr;
    smatch match;
    while(regex_search(expression, match, regex("\\d+"))){
        split_expr.push_back(match.str());
        expression = match.suffix().str();
        string op{expression[0]};
        split_expr.push_back(op);
    }


    // * + -
    answer = abs(stoll(subtract(add(multiply(split_expr)))[0]));
    // * - +
    res = abs(stoll(multiply(add(subtract(split_expr)))[0]));
    if(answer < res) answer = res;
    // + - *
    res = abs(stoll(multiply(subtract(add(split_expr)))[0]));
    if(answer < res) answer = res;
    // - + *
    res = abs(stoll(subtract(add(multiply(split_expr)))[0]));
    if(answer < res) answer = res;
    // + * -
    res = abs(stoll(subtract(multiply(add(split_expr)))[0]));
    if(answer < res) answer = res;
    // - * +
    res = abs(stoll(add(multiply(subtract(split_expr)))[0]));
    if(answer < res) answer = res;

    return answer;
}

---

문제

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

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

728x90

---

[접근1]

연산자와 숫자를 분리한다.

숫자를 regex_search를 사용해서 찾은 뒤 vector에 넣고, 남은 문장의 맨 앞이 연산자일것이므로 집어넣어준다.

(한 문자는 string으로 인식을 못해서 string op{char};와 같은 방법을 사용했다.)

남은 string으로 반복한다.

// split
vector<string> split_expr;
smatch match;
while(regex_search(expression, match, regex("\\d+"))){
    split_expr.push_back(match.str());
    expression = match.suffix().str();
    string op{expression[0]};
    split_expr.push_back(op);
}

---

[접근2]

더하기 빼기 곱하기에 관한 함수를 만든다.

각 함수에선 위에서 만들어둔 vector안에서 각 연산자를 찾고, 앞 뒤에는 숫자가 있을것이므로 그 숫자를 long long인 a, b에 대입 후 해당 연산을 한다. 찾았던 연산자와 그 앞뒤 숫자를 vector에서 erase하고 새로 계산한 숫자를 string으로 만들어서 insert한다. 다음 연산자를 찾고, 없으면 while문을 빠져 나가서 vector를 return해준다.

vector<string> add(vector<string> str){
    auto iter = find(str.begin(), str.end(), "+");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a+b));
        iter = find(str.begin(), str.end(), "+");
    }
    return str;
}

vector<string> subtract(vector<string> str){
    auto iter = find(str.begin(), str.end(), "-");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a-b));
        iter = find(str.begin(), str.end(), "-");
    }
    return str;
}

vector<string> multiply(vector<string> str){
    auto iter = find(str.begin(), str.end(), "*");
    while(iter != str.end()){
        long long a = stoll(*(iter-1)), b = stoll(*(iter+1));
        str.erase(iter-1, iter+2);
        str.insert(iter-1, to_string(a*b));
        iter = find(str.begin(), str.end(), "*");
    }
    return str;
}

---

[접근3]

vector를 정한 연산 순서대로 계산하고 계산이 끝나면 vector에는 하나의 숫자만 남는다.

그 숫자를 stoll을 사용해서 long long으로 변환시켜주고 abs를 사용해서 절대값을 구한다.

전에 구한 값들과 비교하며 제일 큰 값을 구한다.

// * + -
answer = abs(stoll(subtract(add(multiply(split_expr)))[0]));
// * - +
res = abs(stoll(multiply(add(subtract(split_expr)))[0]));
if(answer < res) answer = res;

// + - *
res = abs(stoll(multiply(subtract(add(split_expr)))[0]));
if(answer < res) answer = res;
// - + *
res = abs(stoll(subtract(add(multiply(split_expr)))[0]));
if(answer < res) answer = res;
// + * -
res = abs(stoll(subtract(multiply(add(split_expr)))[0]));
if(answer < res) answer = res;
// - * +
res = abs(stoll(add(multiply(subtract(split_expr)))[0]));
if(answer < res) answer = res;