본문 바로가기
  • 실행력이 모든걸 결정한다
Algorithm/기타 알고리즘

[시뮬레이션] 수식 최대화 - 2020 카카오 인턴십

by 김코더 김주역 2022. 5. 14.
반응형

해결 방법

(i) 문자열을 파싱하여 정수 부분과 연산자 부분을 따로 추출하여 벡터에 저장한다.

(ii) 우선 순위를 배정한다. 우선순위에 대한 경우의 수는 6이기 때문에 6가지 경우만 시뮬레이션 하면 된다.

(iii) 남아 있는 연산자들 중 가장 우선 순위가 높은 연산자를 찾아서, 해당 연산자에 대한 연산을 수행한다.

(iv) 연산 결과는 합쳐서 정수 벡터에 반영하고, 사용한 연산자는 연산자 벡터에서 제거하고, 남은 해당 연산자 카운트를 1 감소시킨다. 이렇게 하면 연산마다 정수 벡터와 연산자 벡터의 크기는 각각 1씩 줄어들 것이고, 모든 연산을 수행했을 때는 정수 결과값 하나만 남게 된다.

(v) 모든 경우에 대한 정수 결과값들의 최댓값을 구한다.

 

 

소스 코드

#include <string>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>

using namespace std;
vector<long long> nv, nvc; // 정수 부분 추출
vector<char> no, noc; // 연산자 부분 추출
int opern[3]; // +, -, * 연산자 개수
map<char, int> m;
int prior[6][3]={{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};

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


long long solution(string expression) {
    long long answer = 0;
    int p=0;
    
    //문자열 파싱
    for(int i=0;i<expression.length();i++){
        if(expression[i]=='+'||expression[i]=='-'||expression[i]=='*'){
            nv.push_back(stoi(expression.substr(p, i-p)));
            no.push_back(expression[i]);
            p=i+1;
        }
    }
    nv.push_back(stoi(expression.substr(p)));
    
    // 우선순위에 대한 모든 경우를 탐색
    for(int i=0;i<6;i++){
        long long cal_result, highest_priority;
        m['+']=prior[i][0]; m['-']=prior[i][1]; m['*']=prior[i][2]; // 우선 순위 부여
        nvc.resize(nv.size()); copy(nv.begin(), nv.end(), nvc.begin());
        noc.resize(no.size()); copy(no.begin(), no.end(), noc.begin());
        memset(opern, 0, sizeof(opern));
        for(int j=0;j<noc.size();j++) opern[m[noc[j]]]++; // 각 연산자 수 카운트
        while(!noc.empty()){
            for(int j=0;j<3;j++){ // 남아 있는 연산자들 중 우선순위가 가장 큰 연산자를 탐색
                if(opern[j]) {
                    highest_priority=j;
                    break;
                }
            }
            for(int j=0;j<noc.size();j++){ // 우선순위가 가장 큰 연산자에 대한 연산을 수행
                if(m[noc[j]]==highest_priority){
                    cal_result=cal(nvc[j], nvc[j+1], noc[j]);
                    nvc[j]=cal_result;
                    nvc.erase(nvc.begin()+j+1, nvc.begin()+j+2);
                    noc.erase(noc.begin()+j, noc.begin()+j+1);
                    opern[highest_priority]--;
                    break;   
                }
            }
        }
        nvc[0]=(nvc[0]>0)?nvc[0]:nvc[0]*(-1);
        answer=max(answer, nvc[0]);
    }
    return answer;
}

 

테스트케이스 30개 모두 통과

반응형

댓글