알고리즘(C++) / 프로그래머스 level 2 : 수식 최대화

level 2 : 수식 최대화

https://programmers.co.kr/learn/courses/30/lessons/67257?language=cpp 

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

 

코드

//프로그래머스 수식 최대화
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib> //절대값
#include <algorithm>

using namespace std;

vector<vector<string>> operation = { {"*", "+", "-"},{"*", "-", "+"}, {"+", "*", "-"}, {"+", "-", "*"}, {"-", "*", "+"}, {"-", "+", "*"} };

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

    //vector v에 숫자와 연산 push
    vector <string> v; 
    string num = "";
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] >= '0' && expression[i] <= '9') {
            num += expression[i];
        }
        else {
            v.push_back(num); //수
;           num = expression[i];
            v.push_back(num); //문자
            num = "";
        }
    }
    v.push_back(num); //마지막 수

    vector<long long> answer_list;
    for (int i = 0; i < 6; i++) { //조합 6개
        vector <string> vec;
        vec = v;
        for (int j = 0; j < 3; j++) { //문자 우선 순위
            while (find(vec.begin(), vec.end(), operation[i][j]) !=vec.end()) {
                auto it = find(vec.begin(), vec.end(), operation[i][j]);

                //연산
                long long n;
                if (operation[i][j] == "*") {
                    n = stoll(vec[it - vec.begin() - 1]) * stoll(vec[it - vec.begin() + 1]);
                }
                else if (operation[i][j] == "+") {
                    n = stoll(vec[it - vec.begin() - 1]) + stoll(vec[it - vec.begin() + 1]);
                }
                else {
                    n = stoll(vec[it - vec.begin() - 1]) - stoll(vec[it - vec.begin() + 1]);
                }
                vec[it - vec.begin() - 1] = to_string(n); //연산 값
                vec.erase(it, it + 2); // 문자 삭제
            }
        }
        answer = max(answer, abs(stoll(vec[0]))); //최대값 찾기
    }

    return answer;
}

int main() {
    string expression = "100-200*300-500+20";
    cout << solution(expression) << "\n";
    return 0;
}

 

설명

• string expression을 숫자와 연산기호로 나눠 벡터에 저장한다.
• *, +, - 으로 만들 수 있는 조합은 6개이다. operation에 string형태로 모든 조합을 저장한다. 
• 우선 순위대로 문자를 찾는다.
• 문자를 찾아 문자 앞 숫자와 문자 뒤 숫자를 연산한다. 
• 기호 앞 숫자를 연산 값으로 변경하고 그 뒤 두 위치는 삭제한다.
• 기호가 존재하지 않을때까지 진행하고 연산한 결과값의 절댓값이 가장 큰 값이지 판단하여 answer에 저장한다. 

 

고찰

걸린시간 : 1시간 반

오래 걸릴 문제는 아니었지만, string형과 char형의 혼돈, erase 사용 방법 등 헷갈리는 부분들이 있어서 구글링 하면서 문제를 풀다 보니까 꽤 오래 걸렸다.

string 형에서 하나의 문자만 뽑아내면 그 문자는 char 형이 된다. 하지만 그것을 인지하지 못하고 find줄에서 char형으로 문자를 찾으면 vec에는 string형으로 저장되어 있으므로 찾을 수 없다. 이런 string형, char형을 구분하지 못하여 오류가 발생하는 부분들이 있었다. 

 

다른 사람이 푼 해결 방법을 보면 숫자와 연산기호를 다른 벡터에 저장하였다. 이렇게 저장하면 문제풀기에도 더 쉬울 거 같다. 형이 다른 string이 들어온다면 다른 벡터에 저장하는 것도 좋은 방법인 거 같다. 

 

char -> string

char c = 'a';
string s = "";
s = c;

char형을 string형으로 변경해주려면 다음과 같이 변경해주어야한다. to_string으로는 string형으로 변환이 불가능하다. 

 

erase, remove

벡터에서 값을 삭제하기 위해서 erase 또는 remove를 사용한다.

remove는 일치하는 모든 요소를 삭제한다. 벡터의 개수는 줄어들지 않는다. 

erase는 삭제할 위치를 삭제한다. 벡터의 개수가 줄어든다. 

erase(시작 위치, 마지막 전 위치); //여러개 삭제
erase(시작 위치); //한개 삭제

 

next_permutation

조합을 구할 수 있다. vector가 무조건 오름차순으로 되어있어야 모든 조합을 구할 수 있다. 전보다 작은 값은 반환하지 않는다. 

#include <algorithm>
vector <int> v = { 1,2,3,4 }; //무조건 오름차순
do {
    for (int i = 0; i < 4; i++) {
        cout << v[i] << " ";
    }
    cout << endl;
} while (next_permutation(v.begin(), v.end()));