개발자 김수진
[프로그래머스] 수식 최대화(C++) 본문
[문제]
programmers.co.kr/learn/courses/30/lessons/67257
[풀이]
next_permutation 함수를 사용해 완전탐색으로 풀었다.
먼저 vector에 숫자와 연산자를 구분해서 담아줬다.
그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다.
우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식으로 풀었다.
next_permutation 함수 : 순열을 구한다.
예를 들어 집합 { '+' , '-' , '*' }의 모든 순열을 구하면 아래와 같이 총 6가지가 나오게 된다.
{ '+' , '-' , '*'}
{ '+' , '*' , '-'}
{ '-', '+' , '*' }
{ '-' , '*' , '+'}
{ '*' ,'+' , '-' }
{ '*' , '-' , '+'}
[코드]
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long calc(long long a,long long b, char op)
{
if(op == '-') return a-b;
else if(op == '+') return a+b;
else return a*b;
}
long long solution(string expression) {
long long answer = 0;
vector <char> oper_list = { '*', '+', '-' };
vector <long long> number;
vector <char> oper;
string num = "";
for(int i=0;i<expression.size();i++)
{
if(expression[i] == '+' || expression[i] =='*' || expression[i] == '-')
{
oper.push_back(expression[i]);
number.push_back(atoi(num.c_str()));
num="";
}
else num+= expression[i];
}
number.push_back(atoi(num.c_str()));
long long _max =0;
do{
vector <char> tmp_oper = oper;
vector <long long> tmp_num = number;
for(int i=0;i<3;i++)
{
for(int j=0;j<tmp_oper.size();j++)
{
if(tmp_oper[j] == oper_list[i])
{
tmp_num[j] = calc(tmp_num[j],tmp_num[j+1],oper_list[i]);
tmp_num.erase(tmp_num.begin()+j+1);
tmp_oper.erase(tmp_oper.begin()+j);
j--;
}
}
}
if(_max < abs(tmp_num[0])) _max = abs(tmp_num[0]);
}while(next_permutation(oper_list.begin(),oper_list.end()));
answer = _max;
return answer;
}
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 징검다리 건너기(C++) (0) | 2021.04.28 |
---|---|
[프로그래머스] 튜플(C++) (0) | 2021.04.27 |
[프로그래머스] 키패드 누르기(C++) (0) | 2021.04.18 |
[프로그래머스] 소수 찾기 (0) | 2020.11.10 |
[프로그래머스] 큰 수 만들기 (0) | 2020.11.10 |