[C++, Python] 카카오 2020 인턴쉽 코딩테스트 - 수식 최대화

프로그래머스 67257

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

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

수식은 총 세가지이다.

어떤 수식이 나오던 우선순위 종류의 최대 갯수는 3!인 6개이다

 

1. C++

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

using namespace std;

long long solution(string expression) {
    long long answer = 0;
    vector<long long> num;
    vector<char> exp, loc;
    string n = "";

    for (int i = 0; i < expression.size(); i++) 
    {
        if (expression[i] == '*' || expression[i] == '+' || expression[i] == '-')
        {
            // 수식 찾으면 그 앞까지 숫자 변환후 저장
            num.push_back(stoi(n));
            n = "";
            // exp에 저장되지 않은 수식이면 exp에 추가
            if (find(exp.begin(), exp.end(), expression[i]) == exp.end())
                exp.push_back(expression[i]);
            //loc에 수식 추가
            loc.push_back(expression[i]);
        }
        else n += expression[i];
    }
    // 마지막은 숫자로 끝나니 num에 추가
    num.push_back(stoi(n));

    //next_permutation 위해
    sort(exp.begin(), exp.end());

    do
    {
        vector<long long>tmp_num = num;
        vector<char> tmp_loc = loc;

        for (int i = 0; i < exp.size(); i++) {
            for (int j = 0; j < tmp_loc.size(); j++) {
                if (exp[i] == tmp_loc[j]) {
                    //계산 값 갱신
                    if (tmp_loc[j] == '+') tmp_num[j] = tmp_num[j] + tmp_num[j + 1];
                    else if (tmp_loc[j] == '-') tmp_num[j] = tmp_num[j] - tmp_num[j + 1];
                    else if (tmp_loc[j] == '*') tmp_num[j] = tmp_num[j] * tmp_num[j + 1];

                    // 뒤에 값, 계산한 수식 지우기
                    tmp_num.erase(tmp_num.begin() + j + 1);
                    tmp_loc.erase(tmp_loc.begin() + j);
                    //tmp_loc 1칸 줄었으니 j--
                    j--;
                }
            }
        }
        //최대값 갱신
        if (answer < abs(tmp_num[0])) answer = abs(tmp_num[0]);
    } while (next_permutation(exp.begin(), exp.end()));


    return answer;
}

https://eunchanee.tistory.com/88

(프로그래머스 c++ KAKAO)수식 최대화

 

2. Python

import re
from itertools import permutations

def solution(expression):
    #expression 에있는 기호 골라내기
    op = [x for x in ['*','+','-'] if x in expression]
    #있는 기호로만 순열
    op = [list(y) for y in permutations(op)]
    # ( : start a capture group,  ) : end a capture group, \d : [0-9]
    ex = re.split(r'(\D)',expression)
    # 테스트1 print(ex) 결과 : ['100', '-', '200', '*', '300', '-', '500', '+', '20']


    a = []
    for x in op:
        _ex = ex[:]
        # x : 기호 순열
        for y in x:
            while y in _ex:
                tmp = _ex.index(y)
                # 해당 기호의 앞칸 숫자 = str(eval(앞칸 숫자 (기호) 뒤칸 숫자))
                #eval : string으로 된 연산 계산하기
                _ex[tmp-1] = str(eval(_ex[tmp-1]+_ex[tmp]+_ex[tmp+1]))
                #사용한 기호와 뒤칸 숫자 지우기
                _ex = _ex[:tmp]+_ex[tmp+2:]
        a.append(_ex[-1])

    return max(abs(int(x)) for x in a)

 

 

 

시골우유님의 코드에 주석을 달았다

 

기호, 숫자 분리를 정규표현식으로 간단하게 작성했고

숫자와 기호를 각각 다른 리스트로 분리하지 않고 계산하고 기호랑 그 뒤에 숫자까지 지웠다

 

C++코드를 그대로 Python으로 바꿨을때 사용한 기호, 숫자를 지우면 index out of range 에러가 난다

ㄷ 

 

배울점

 

1.

수식의 우선순위 종류는 몇 종류 안되니 배열로 만들어서 for문을 돌릴까 했는데

next_next_permutation 를 사용해 순열을 만들면 되는거였다. 

 

 

2. 

숫자를 추출 하는 것도 이전에는 for문을 돌리면서  Ascii 코드 값을 이용해 숫자인지 아닌지 판별하는 것보다 

맨 처음과 맨 마지막은 숫지아니

if (수식기호이면) ~
else number_str += expression[i] 

이런 식으로 해서 수식이 나오면 지금까지의 stoi(number_str) 하면 되는 것이었다.

 

 

나머지 공부

1. next_premutation 이용해 순열, 조합, 중복 순열, 중복 조합 연습하기

2. next_premutation 없이순열, 조합, 중복 순열, 중복 조합 연습하기

3.c++,  Python 으로 위의 코드 다시 짜보기

 

 

2020 카카오 인턴십 문제 해설

https://tech.kakao.com/2020/07/01/2020-internship-test/