Programers : 수식 최대화 -next_permutation()
23850 단어 level2PROGRAMERSPROGRAMERS
수식 최대화
코드
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cmath>
using namespace std;
long long solution(string expression) {
long long answer = 0;
int arr[3] = {'+','-','*'};
vector<char> ch;
/* 식에 연산자가 몇종류 있는지 구하기 */
for(int i=0;i<3;i++) {
auto it = find(expression.begin(), expression.end(), arr[i]);
if(it != expression.end()) ch.push_back(arr[i]);
}
int untill = 1;
for(int i=ch.size();i>=1;i--) untill*=i;
/* 연산자 개수만큼 경우의수 구하기 */
vector<int> tmp(ch.size());
vector<vector<string>> v(untill);
for(int i=0;i<tmp.size();i++) tmp[i] = i;
int q=0;
do{
for(int i=0;i<tmp.size();i++){
string t ="";
t += ch[tmp[i]];
v[q].push_back(t);
}
q++;
}while(next_permutation(tmp.begin(), tmp.end()));
/* expression을 숫자와 기호로 나누기 */
stringstream ss(expression);
vector<string> s;
int n;char c;
while(true)
{
ss >> n;
s.push_back(to_string(n));
if(ss.eof()) break;
ss >> c;
string t="";
t+=c;
s.push_back(t);
}
/* 계산 하기 */
long long MAX = 0;
for(int i=0;i<v.size();i++)
{
vector<string> temp(s);
for(int j=0;j<v[i].size();j++)
{
for(int z=0;z<temp.size();z++)
{
if(temp[z] == v[i][j]){
long long n1 = stoll(temp[z-1]);
long long n2 = stoll(temp[z+1]);
long long result;
if(v[i][j] == "+") result = n1+n2;
else if(v[i][j] == "-") result = n1-n2;
else if(v[i][j] == "*") result = n1*n2;
temp.erase(temp.begin()+z+1);
temp.erase(temp.begin()+z);
temp[z-1] = to_string(result);
z -=2;
}
}
}
MAX = max(MAX,abs(stoll(temp.front())));
}
answer = MAX;
return answer;
}
- key point!
: 연산자의 종류 개수에 따라 가능한 조합을 구하는 것이 관건
<algorithm>
에 next_permutation()
을 이용하면 현재 조합에서 다음 순열을 구할 수 있음!
/* 연산자 개수만큼 경우의수 구하기 */
vector<int> tmp(ch.size());
vector<vector<string>> v(untill);
for(int i=0;i<tmp.size();i++) tmp[i] = i;
int q=0;
do{
for(int i=0;i<tmp.size();i++){
string t ="";
t += ch[tmp[i]];
v[q].push_back(t);
}
q++;
}while(next_permutation(tmp.begin(), tmp.end()));
- tmp배열에 [0, 1, 2, 3, 4] 가 있을 때
[0,1,2,3,4] ~ [4,3,2,1,0] 까지 모든 조합으로 바꾸어 준다
- 반환형은
bool
형이기 때문에 조건으로 사용!
prev_permutation()
을 사용하면 이 전 조합으로도 갈 수 있음!
Author And Source
이 문제에 관하여(Programers : 수식 최대화 -next_permutation()), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-수식-최대화-nextpermutation
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#include <string> #include <vector> #include <algorithm> #include <sstream> #include <iostream> #include <cmath> using namespace std; long long solution(string expression) { long long answer = 0; int arr[3] = {'+','-','*'}; vector<char> ch; /* 식에 연산자가 몇종류 있는지 구하기 */ for(int i=0;i<3;i++) { auto it = find(expression.begin(), expression.end(), arr[i]); if(it != expression.end()) ch.push_back(arr[i]); } int untill = 1; for(int i=ch.size();i>=1;i--) untill*=i; /* 연산자 개수만큼 경우의수 구하기 */ vector<int> tmp(ch.size()); vector<vector<string>> v(untill); for(int i=0;i<tmp.size();i++) tmp[i] = i; int q=0; do{ for(int i=0;i<tmp.size();i++){ string t =""; t += ch[tmp[i]]; v[q].push_back(t); } q++; }while(next_permutation(tmp.begin(), tmp.end())); /* expression을 숫자와 기호로 나누기 */ stringstream ss(expression); vector<string> s; int n;char c; while(true) { ss >> n; s.push_back(to_string(n)); if(ss.eof()) break; ss >> c; string t=""; t+=c; s.push_back(t); } /* 계산 하기 */ long long MAX = 0; for(int i=0;i<v.size();i++) { vector<string> temp(s); for(int j=0;j<v[i].size();j++) { for(int z=0;z<temp.size();z++) { if(temp[z] == v[i][j]){ long long n1 = stoll(temp[z-1]); long long n2 = stoll(temp[z+1]); long long result; if(v[i][j] == "+") result = n1+n2; else if(v[i][j] == "-") result = n1-n2; else if(v[i][j] == "*") result = n1*n2; temp.erase(temp.begin()+z+1); temp.erase(temp.begin()+z); temp[z-1] = to_string(result); z -=2; } } } MAX = max(MAX,abs(stoll(temp.front()))); } answer = MAX; return answer; }
- key point!
: 연산자의 종류 개수에 따라 가능한 조합을 구하는 것이 관건<algorithm>
에next_permutation()
을 이용하면 현재 조합에서 다음 순열을 구할 수 있음!/* 연산자 개수만큼 경우의수 구하기 */ vector<int> tmp(ch.size()); vector<vector<string>> v(untill); for(int i=0;i<tmp.size();i++) tmp[i] = i; int q=0; do{ for(int i=0;i<tmp.size();i++){ string t =""; t += ch[tmp[i]]; v[q].push_back(t); } q++; }while(next_permutation(tmp.begin(), tmp.end()));
- tmp배열에 [0, 1, 2, 3, 4] 가 있을 때
[0,1,2,3,4] ~ [4,3,2,1,0] 까지 모든 조합으로 바꾸어 준다- 반환형은
bool
형이기 때문에 조건으로 사용!prev_permutation()
을 사용하면 이 전 조합으로도 갈 수 있음!
Author And Source
이 문제에 관하여(Programers : 수식 최대화 -next_permutation()), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-수식-최대화-nextpermutation저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)