[프로그래머스] 수식 최대화
✔️ 문제
- 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/67257
- 카카오 기술블로그 문제 해설 : https://tech.kakao.com/2020/07/01/2020-internship-test/
- 2020 카카오 인턴 채용 코딩테스트 기출문제다.
✔️ 문제 이해
-
모든 참가자들에게는 숫자들과 3가지의 연산문자(
+, -, *) 만으로 이루어진 연산 수식이 전달된다. -
참가자들은 연산자 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출해야한다.
- 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 한다.
-
참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해야한다.
✔️ 알고리즘 설계
- 표현식으로부터 숫자와 연산자를 추출해서 숫자 벡터와 연산자 벡텅에 넣는다.
- 표현식에 등장하는 연산자를 중복되지 않도록 우선순위 정보 벡터에 넣는다.
- 우선순위 정보 벡터에서 뒤에 있는 연산자일수록 우선순위가 낮은 연산자라고 정의한다.
- 따라서 우선순위 정보 벡터에 대한 모든 순열은 곧 모든 연산자 우선순위 조합이다. (
next_permutation을 활용한다.)
- 숫자, 연산자, 연산자 우선순위 정보를 벡터, next_permutation을 활용하여, 모든 연산자 우선순위를 만들어보며 최대값을 찾는다.
👨🏻💻 소스 코드
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
long long cal(vector<long long> num , vector<char> oper, vector<char> operPirority) {
// 주어진 연산자 우선순위 벡터의 연산자를 순차적으로 탐색한다.
// (operPirority에 들어있는 연산자 순서가 우선순위 순서다.)
for (char priority : operPirority) {
for (int i = 0; i < oper.size(); i++) {
if (oper[i] == priority) { // 연산자와 숫자가 들어있는 각 벡터를 탐색하며 계산한다.
long long calResult;
if (priority == '*') {
calResult = num[i] * num[i + 1];
}
else if(priority == '+') {
calResult = num[i] + num[i + 1];
}
else if (priority == '-') {
calResult = num[i] - num[i + 1];
}
num[i] = calResult;
num.erase(num.begin() + i + 1);
oper.erase(oper.begin() + i);
i--;
}
}
}
return abs(num[0]); // 절대값을 리턴한다.
}
long long solution(string expression) {
long long answer = 0;
vector<char> oper; // 연산자를 담는 벡터
vector<long long> num; // 숫자를 담는 벡터
vector<char> operPirority; // 연산자 우선순위를 담는 벡터
string tmpNum = "";
bool check[1000000];
memset(check, false, sizeof(check));
// 주어진 표현식에서 연산자와, 숫자를 추출한다.
for (int i = 0; i < expression.size(); i++) {
if (isdigit(expression[i])) { // 숫자 문자일 경우 tmpNum에 임시저장.
tmpNum += expression[i];
} else if (expression[i] == '+' // 연산자일경우
|| expression[i] == '-'
|| expression[i] == '*') {
// 표현식에 등장한 연산자를 한 번씩만 넣는다.
// operPirority 벡터는 연산자 우선순위를 표현하는 용도이다.
if (!check[expression[i]]) {
check[expression[i]] = true;
operPirority.push_back(expression[i]);
}
oper.push_back(expression[i]); // 연산자 벡터에 넣는다.
num.push_back(stoi(tmpNum)); // tmpNum을 숫자로 바꿔서 숫자 벡터에 넣는다.
tmpNum = ""; // 다음 숫자를 담기위해 tmpNum 초기화
}
}
num.push_back(stoi(tmpNum)); // 마지막 숫자를 넣는다.
// operPirority에 들어있는 연산자들에 대하여 순열을 구한다.
// 모든 순열을 구한다는 것 == 모든 우선순위 조합을 구한다는 것.
sort(operPirority.begin(), operPirority.end());
do {
// 숫자를 담은 벡터, 연산자를 담은 벡터,
// next_permutation으로 구한 연산자 우선순위가 들어있는 벡터를
// cal 함수의 인자로 넣어주고 수식 계산을한다.
// 계산의 결과에 대해 최대값 여부를 확인하고 갱신한다.
answer = max(answer, cal(num, oper, operPirority));
} while (next_permutation(operPirority.begin(), operPirority.end()));
return answer;
}
✔️ 문제 회고
next_permutation을 잘 활용했다.