문제 푼 날짜 : 2021-09-01

문제

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

접근 및 풀이

문제를 봤을 때, 입력의 크기가 그렇게 크지 않아서 완전탐색 문제라고 판단하였고, 아래의 순서대로 코드를 구현해주었다.

1. 주어진 수식(expression)을 순회하면서 연산자와 피연산자를 구분하여 vector에 넣어주었다.
2. 문제의 핵심이라고 생각했던 것은 연산자의 우선순위를 정하여 계산을 해야한다는 것이다.
   2-1. 이는 어떻게 할지 고민하다가 algorithm 헤더에 있는 next_permutation 함수를 이용하였다. (코드의 op변수)
3. next_permutation을 통해 순서가 정해진 연산자(op)를 순서대로 순회하며 해당하는 연산자(Optr) 앞,뒤에 있는 피연산자를 계산하고 그 값을 업데이트 해주었다.
   3-1. 계산을 한 피연산자를 vector에서 계속해서 저장하기 위해 A + B = C 였다면, A를 C로 바꿔주고 B 값을 erase해주었다.
   3-2.연산자도 마찬가지로 계산된 후에 erase 해준다.
4. 잘못된 연산식은 입력으로 주어지지 않는다고 했으니, 끝까지 계산하면 하나의 값이 남으며 그 값의 절대값 중 가장 큰 값을 찾아 return 해준다.

코드

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

using namespace std;

long long calculate(long long a, long long b, char op) {
    switch (op) {
        case '+' :
            return a + b;
        case '-' :
            return a - b;
        case '*' :
            return a * b;
    }
}

long long solution(string expression) {
    long long answer = 0;
    vector<long long> opnd;
    vector<char> optr;
    // vector<char> op;
    vector<char> op{ '+', '-', '*' };
    
    string tmp = "";
    for (char ch : expression) {
        if (isdigit(ch)) {
            tmp += ch;
        } else {
            opnd.push_back(stoll(tmp));
            optr.push_back(ch);
            // op.push_back(ch);
            tmp = "";
        }
    }
    opnd.push_back(stoi(tmp));
    
    sort(op.begin(), op.end());
    // op.erase(unique(op.begin(), op.end()), op.end());
    
    do {
        vector<long long> Opnd = opnd;
        vector<char> Optr = optr;
        
        for (char ch : op) {
            for (int i = 0; i < Optr.size();) {
                if (Optr[i] == ch) {
                    Opnd[i] = calculate(Opnd[i], Opnd[i + 1], Optr[i]);
                    Opnd.erase(Opnd.begin() + i + 1);
                    Optr.erase(Optr.begin() + i);
                } else {
                    i++;
                }
            }
        }
        answer = max(answer, abs(Opnd.front()));
    } while(next_permutation(op.begin(), op.end()));
    
    return answer;
}

결과

피드백

C++ STL 표준 라이브러리를 잘 활용하여 구현하는 연습을 하자.