[Lev.2] 수식 최대화(C++)

1. 문제 

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

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

 

2. 접근 방법

1) 우선 "숫자"와 "연산자"를 나누어 준다. 

2) 연산자 별 우선순위 경우의 수를 next_permutation으로 만들어서 각 경우의 수 별로 연산을 수행한다.

3) 우선순위에 해당하는 연산자를 발견하면, 연산자 기준 양 옆의 숫자를 연산하여 연산 결과를 다시 list에 넣는다.

 

-> 중간에 삽입/삭제가 자주 있으므로 list를 사용해야 한다.

 

3. 실수했던 부분 & 처음 알았던 부분

1) iterator 접근 방법

    - iterator는 +연산,- 연산을 지원하지 않는다!!!!(iterator +=2 같은 게 안된다는 의미)

    => iter = next(iter, 2) ; 혹은 advence(iter,2); 를 사용하자.

    => iter = prev(iter,2);

 

2) containter 별 장단점

 

*  시퀀스 컨테이너 

 - 예 : 

 - 특징 :

 - 장점:

 - 단점 

 

 

3) string을 연산자와 숫자로 나누는 법 (다른 고민 생각하지 말고 바로 이 방식 사용하기)

    //수식을 숫자와 연산자로 나누어서 리스트에 저장
    int idx = 0;
    for (int i=0;i<expression.length();i++) {
        if(expression[i] < '0' || expression[i] > '9') {
            li.push_back(expression.substr(idx,i-idx)); //idx부터 (i-idx)개수만큼 숫자로 저장
            li.push_back(string(1,expression[i])); // 연산자 부분 자르기
            idx = i+1;
        }
    } 
    //마지막 부분까지 처리 해야 한다.
    li.push_back(expression.substr(idx));

 

4. 코드

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

string cal(string num1, string op, string num2) {
    long long ret = 0;
    if(op == "*") ret = stol(num1) * stol(num2);
    else if (op == "+") ret = stol(num1) + stol(num2);
    else ret = stol(num1) - stol(num2);
    return to_string(ret);   
}

long long getNum(list <string> li, string *prior) {
    for (int i =0; i <3; i++) {
        string op = prior[i];
        for(list<string>::iterator iter = li.begin(); iter!= li.end();) {
         //현재 우선순위의 연산자 찾으면 연산자 기준 양 옆의 수로 계산
         if(*iter== op) {
             string newNum = cal(*prev(iter,1),op,*next(iter,1)); //계산한 값
             iter = li.erase(prev(iter,1),next(iter,2)); //피연산자 2개,연산자 제거
             li.insert(iter,newNum); // 계산한 값 삽입
         }   
        else iter++;    
        }
    }
    return abs(stol(li.front()));
}

long long solution(string expression) {
    long long answer = 0;
    string prior[3] = { "*","+","-"};
    list< string > li;
    int idx = 0;
    //수식을 숫자와 연산자로 나누어서 리스트에 저장
    for (int i=0;i<expression.length();i++) {
        if(expression[i] < '0' || expression[i] > '9') {
            li.push_back(expression.substr(idx,i-idx));
            li.push_back(string(1,expression[i]));
            idx = i+1;
        }
    } 
    li.push_back(expression.substr(idx));
    
    //경우의 수만큼 함수 호출
    do {
        answer = max(answer,getNum(li,prior));
    }while(next_permutation(prior,prior+3));
    
    return answer;
}