[C++로 풀이] 수식 최대화 ⭐⭐

📌 수식 최대화

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

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

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

    vector<long long> record_operand;
    vector<char> record_operator;
    string temp = "";
    for (int i = 0; i < expression.length(); i++) {
        if (expression[i] >= '0' && expression[i] <= '9')
            temp += expression[i];
        else {
            record_operator.push_back(expression[i]);
            record_operand.push_back(stoll(temp));
            temp = "";
        }
    }
    record_operand.push_back(stoll(temp));

    vector<int> perm = { 0, 1, 2 };
    string op = "+-*";
    do {
        vector<long long> temp_operand = record_operand;
        vector<char> temp_operator = record_operator;
        for (int i = 0; i < perm.size(); i++) {
            for (int j = 0; j < temp_operator.size(); ) {
                if (temp_operator[j] == op[perm[i]]) {
                    long long res = calculate(temp_operand[j], temp_operand[j + 1], temp_operator[j]);

                    temp_operand.erase(temp_operand.begin() + j);
                    temp_operand.erase(temp_operand.begin() + j);
                    temp_operand.insert(temp_operand.begin() + j, res);

                    temp_operator.erase(temp_operator.begin() + j);
                }
                else
                    j++;
            }
        }
        answer = max(answer, abs(temp_operand[0]));
    } while (next_permutation(perm.begin(), perm.end()));

    return answer;
}

✈ 연산자와 피연산자 구분하기

    vector<long long> record_operand;
    vector<char> record_operator;
    string temp = "";
    for (int i = 0; i < expression.length(); i++) {
        if (expression[i] >= '0' && expression[i] <= '9')
            temp += expression[i];
        else {
            record_operator.push_back(expression[i]);
            record_operand.push_back(stoll(temp));
            temp = "";
        }
    }
    record_operand.push_back(stoll(temp));

• “100-200*300-500+20” 을 예로 들자면
  • record_operand 👉 {100, 200, 300 , 500, 20}
  • record_operator 👉 {‘-‘, ‘*’, ‘-‘, ‘+’}
• 필연적으로 피연산자의 총 개수가 연산자의 총 개수보다 딱 한개 더 많을 수 밖에 없다.
• operand[i]와 operand[i + 1] 두 피연산자를 operator[i] 연산자로 연산하는 인덱스 규칙을 가진다.

맨 끝에는 연산자가 없다. 연산자를 만날 때만 record_operand 에 피연산자를 추가했었기 때문에 for문이 끝나고 나오면 마지막 피연산자가 아직 record_operand 에 추가가 되지 못한 상태일 것이다. 그래서 for문 나와서 한번 더 추가를 해준다. 코드를 이렇게 특정 경우에만 어떤 요소가 반영 되도록 짜는 경우엔 반복문이 끝나고 마지막 요소가 반영되지 못하지는 않을까 하는 생각을 꼭 하자.

✈ 연산자끼리의 순열 (우선순위 순서 종류는 3! = 6가지)

    vector<int> perm = { 0, 1, 2 };
    string op = "+-*"; // '+' 의 인덱스 0. '-' 의 인덱스 1. '*' 의 인덱스 2.
    do {
        vector<long long> temp_operand = record_operand;
        vector<char> temp_operator = record_operator;
        for (int i = 0; i < perm.size(); i++) {
            for (int j = 0; j < temp_operator.size(); ) {
                if (temp_operator[j] == op[perm[i]]) {  // 연산자 찾은 경우 연산 시작! 
                    long long res = calculate(temp_operand[j], temp_operand[j + 1], temp_operator[j]);

                    temp_operand.erase(temp_operand.begin() + j);
                    temp_operand.erase(temp_operand.begin() + j); // 위의 삭제로 앞으로 한칸 땡겨져 왓을테니 그대로 j 위치 삭제하면 된다.
                    temp_operand.insert(temp_operand.begin() + j, res); // 위의 삭제로 앞으로 한칸 땡겨져 왓을테니 그대로 j 위치에 삽입하면 된다.

                    temp_operator.erase(temp_operator.begin() + j);
                    // 이 경우엔 j++ 하지 않는다. temp_operator 원소가 삭제되어서 앞으로 한 칸 땡겨졌을테니 그대로 다음 반복에서 j 인덱스 검사하면 된다.
                }
                else
                    j++;  // 이번 연산자 못 찾은 경우에만 j++
            }
        }
        answer = max(answer, abs(temp_operand[0])); // answer에는 최대값만 들어가게끔. 음수는 양수로 바꾼다 했으니 절대값만 취함.
    } while (next_permutation(perm.begin(), perm.end()));

• 순열 구하기
  • 사실 연산자가 3 개 뿐이라 연산자끼리의 나올 수 있는 순열은 3! = 6 가지 뿐이다. 그래서 굳이 next_permutation 안 쓰고 6 가지 연산자 순열을 string 배열에 담아두고 갖다 쓰는게 훨씬 간단하지만 next_permutation 연습 한번 해보려고 일부러 사용했다.
  • next_permutation 은 원소들이 크기를 비교할 수 있어야 사용할 수 있기 때문에 “+-*” 자체를 next_permutation 로 정렬시키며 다음 순열을 구하기엔 애로사항이 있지 않을까 싶었다. 따라서 perm { 0, 1, 2 } 배열을 통하여 이 것을 next_permutation 시키고 연산자는 이 인덱스에 대응하도록 하였다.
    • 예를 들어 현재 perm모양이 {1, 2, 0} 이라면 연산자 우선순위는 * > + > - 인게 된다.
      • 차례대로 [피연산자 * 피연산자 를 모두 계산 👉 피연산자 + 피연산자 를 모두 계산 👉 피연산자 - 피연산자 를 모두 계산] 이 순서대로 반복문을 진행하면 된다.
• 연산 후
  • 두 피연산자 삭제
  • 두 피연산자의 연산 결과 해당 자리에 삽입
  • 연산자 삭제
• 모든 연산이 다 끝나고 난 후 (즉, 해당 순열의 3개의 연산자 모두 연산 완료)
  • 필연적으로 temp_operand에는 하나의 원소만 남게 된다. 이게 연산자 우선순위가 이런 순서일 때의 expression 최종 연산 결과가 된다. (temp_operator는 비워짐)
• 우선순위 순열이 바뀔 때마다 새롭게 연산해야하므로 삭제되어 비워지고 하나밖에 안남은 연산자, 피연산자 집합을 새로 초기화 해야 한다.
  • 그래서 record_operand, record_operator을 그대로 안쓰고 매 순열마다 이를 복사한 temp_operand, temp_operator을 새로 만들어주고 이걸로 연산을 하는 것이다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기