2020 카카오 인턴십 for Tech developers 코딩테스트 2번

문제

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

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

문제 분석

개념은 어렵지 않았으나 1번과 같이 구현이 까다로웠던 문제였던것 같다.

잘못된 연산방식이 나오지 않고, 하나의 연산자는 두개의 수를 연산하는 작업을 하는 것이 조건으로써 주어졌으므로, 나는 수와 연산자 string을 하나하나씩 분리해서 vector에 집어넣고, 하나씩 꺼내면서 우선순위에 맞게 연산하였다.

3개의 연산자에 대해, 순열이므로 3! = 6이고, 전체 문자열의 길이 자체도 30정도로 그렇게 크지 않았기 때문에 brute force하게 접근해도 된다고 생각했다.

그래서 모든 연산 우선순위에 대해서 절대값의 최댓값을 구해보았다. 연산의 우선순위는 그냥 현재 우선순위가 가장 높은 연산자만 찾아서 다 연산시키고, 나머지는 무시하는 방향으로 진행하였다.

우선 수를 뽑은 다음 수 다음 연산자 확인하고 만약 현재 우선순위가 가장 높은 연산자라면, 다음 수를 뽑아서 연산한다.

이렇게 연산된 수를 새로운 vector에 넣었고, 이 연산을 하는 함수를 3가지 만들고 brute force하게 돌렸더니 정답이 나왔다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <math.h>

using namespace std;

vector<string> input_v;
vector<string> origin_v;
vector<string> tmp_v;

long long int string_to_int(string ex)
{
    long long return_val = 0;
    int i=0;
    if(ex[0] == '-')
    {
        i = 1;
    }        
    for(; i<ex.length(); i++)
    {
        return_val *= 10;
        return_val += (ex[i] - '0');
    }
    if(ex[0] == '-')
    {
        return_val *= -1;
    }        
    return return_val;
}

string int_to_string(long long tin)
{
    string a, b;
    if(tin < 0)
    {
        b.push_back('-');
        tin *= -1;
    }
    while(tin > 0)
    {
        a.push_back((tin%10) + '0');
        tin = tin / 10;
    }
    for(int i=a.length()-1; i>=0; i--)
        b.push_back(a[i]);
    return b;
}

void add_all()
{
    tmp_v.clear();
    long long tmp_val = 0;
    for(int i=0; i<input_v.size(); i++)
    {
        if(i%2 == 0)
            tmp_val = string_to_int(input_v[i]);
        else
        {
            if(input_v[i][0] == '+')
                tmp_val += string_to_int(input_v[++i]);
            else
            {
                tmp_v.push_back(int_to_string(tmp_val));
                tmp_v.push_back(input_v[i]);
                tmp_val = 0;
            }
        }
    }
    tmp_v.push_back(int_to_string(tmp_val));
}

void mul_all()
{
    tmp_v.clear();
    long long tmp_val = 1;
    for(int i=0; i<input_v.size(); i++)
    {
        if(i%2 == 0)
            tmp_val = string_to_int(input_v[i]);
        else
        {
            if(input_v[i][0] == '*')
                tmp_val *= string_to_int(input_v[++i]);
            else
            {
                tmp_v.push_back(int_to_string(tmp_val));
                tmp_v.push_back(input_v[i]);
                tmp_val = 1;
            }
        }
    }
    tmp_v.push_back(int_to_string(tmp_val));
}

void sub_all()
{
    tmp_v.clear();
    long long tmp_val = 0;
    for(int i=0; i<input_v.size(); i++)
    {
        if(i%2 == 0)
            tmp_val = string_to_int(input_v[i]);
        else
        {
            if(input_v[i][0] == '-')
                tmp_val -= string_to_int(input_v[++i]);
            else
            {
                tmp_v.push_back(int_to_string(tmp_val));
                tmp_v.push_back(input_v[i]);
                tmp_val = 0;
            }
        }
    }
    tmp_v.push_back(int_to_string(tmp_val));
}

long long solution(string expression) {
    long long answer = 0;
    string tmp;
    for(int i=0; i<expression.length(); i++)
    {
        if(expression[i] == '+' || expression[i] == '*' || expression[i] == '-')
        {
            input_v.push_back(tmp);
            tmp.clear();

            tmp.push_back(expression[i]);
            input_v.push_back(tmp);
            tmp.clear();
        }
        else
            tmp.push_back(expression[i]);
    }
    input_v.push_back(tmp);

    tmp_v = input_v;
    origin_v = input_v;

    add_all();
    input_v  = tmp_v;
    mul_all();
    input_v  = tmp_v;
    sub_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));
    
    input_v = origin_v;
    tmp_v = origin_v;
    
    add_all();
    input_v  = tmp_v;
    sub_all();
    input_v  = tmp_v;
    mul_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));

    input_v = origin_v;
    tmp_v = origin_v;
    
    sub_all();
    input_v  = tmp_v;
    add_all();
    input_v  = tmp_v;
    mul_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));
    

    input_v = origin_v;
    tmp_v = origin_v;
    
    sub_all();
    input_v  = tmp_v;
    mul_all();
    input_v  = tmp_v;
    add_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));

    input_v = origin_v;
    tmp_v = origin_v;
    
    mul_all();
    input_v  = tmp_v;
    sub_all();
    input_v  = tmp_v;
    add_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));

    input_v = origin_v;
    tmp_v = origin_v;
    
    mul_all();
    input_v  = tmp_v;
    add_all();
    input_v  = tmp_v;
    sub_all();
    answer = max(answer, abs(string_to_int(tmp_v[0])));

    
    return answer;
}

개선점?

꽤 길다. 몇가지 마음에 들지 않은점이 있는데, vector를 함수 호출시마다 복사한다는 것

vector의 erase가 n의 복잡도를 갖는다고 생각하고 사용하기를 지양하다 보니 정작 n이 작아서 사용해도 될 타이밍에 사용하지 않았다. 

그리고 함수를 3가지로 나누었지만 사실상 보면 연산과 초기값을 제외한다면 크게 다른것은 없다. 하나의 함수로 나타낼 수 있었어야 했던것 같다.

예를 들면, 인자로 연산자를 받고, if문을 이용해서 현재 연산자와 대치하여 맞으면 연산하는 방향으로 갔으면 더 좋았을것 같다.