쌓고 쌓다
[프로그래머스] 수식 최대화 C++ 풀이 본문
https://school.programmers.co.kr/learn/courses/30/lessons/67257?language=cpp
전체 코드
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<string> v;
vector<string> copy_v;
bool visit[4];
int pri[4]; // + - *
long long ans = 0;
void solve(int idx, int cnt)
{
if (cnt == 3)
{
copy_v = v;
while (copy_v.size() != 1)
{
int pos;
int maxPri = 0;
for (int i = 0; i < copy_v.size(); i++)
{
if (copy_v[i] == "+" && maxPri < pri[1])
{
pos = i;
maxPri = pri[1];
}
else if (copy_v[i] == "-" && maxPri < pri[2])
{
pos = i;
maxPri = pri[2];
}
else if (copy_v[i] == "*" && maxPri < pri[3])
{
pos = i;
maxPri = pri[3];
}
}
long long res = 0; // 이것 int가 아닌 long long으로
if (copy_v[pos] == "+")
res = stoll(copy_v[pos - 1]) + stoll(copy_v[pos + 1]);
else if (copy_v[pos] == "-")
res = stoll(copy_v[pos - 1]) - stoll(copy_v[pos + 1]);
else
res = stoll(copy_v[pos - 1]) * stoll(copy_v[pos + 1]);
copy_v.erase(copy_v.begin() + (pos - 1), copy_v.begin() + (pos + 2));
copy_v.insert(copy_v.begin() + (pos - 1), to_string(res));
}
if (stoll(copy_v[0]) < 0)
copy_v[0].erase(copy_v[0].begin());
ans = max(ans, stoll(copy_v[0]));
return;
}
for (int i = 1; i < 4; i++)
{
if (visit[i] == false)
{
visit[i] = true;
pri[idx] = i;
solve(idx + 1, cnt + 1);
visit[i] = false;
}
}
}
long long solution(string expression) {
long long answer = 0;
string str;
for (int i = 0; i < expression.length(); i++)
{
if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*')
{
v.push_back(str);
str = "";
string s;
s += expression[i];
v.push_back(s);
}
else
str += expression[i];
}
v.push_back(str); // 마지막 수를 안넣었다..
solve(1, 0);
answer=ans;
return answer;
}
조금 지저분하게 코드가 작성되었다...
그냥 간단히 각 연산자에 대해 우선순위를 매겨
그 우선순위를 적용하여 식을 풀어 최대가 되는 값을 찾으면 된다.
string str;
for (int i = 0; i < expression.length(); i++)
{
if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*')
{
v.push_back(str);
str = "";
string s;
s += expression[i];
v.push_back(s);
}
else
str += expression[i];
}
v.push_back(str); // 마지막 수를 안넣었다..
주어진 입력을 수와 연산자로 분리해 저장한다.
void solve(int idx, int cnt)
idx는 현재 인덱스(우선순위를 매길 인덱스) -> pri배열에 pri[1]은 +의 우선순의 pri[2]는 -의 우선순위 pri[3]은 *의 우선순위
cnt는 몇개의 연산자에 대해 우선순위를 매겼는가?
if (cnt == 3)
{
copy_v = v;
while (copy_v.size() != 1)
{
int pos;
int maxPri = 0;
for (int i = 0; i < copy_v.size(); i++)
{
if (copy_v[i] == "+" && maxPri < pri[1])
{
pos = i;
maxPri = pri[1];
}
else if (copy_v[i] == "-" && maxPri < pri[2])
{
pos = i;
maxPri = pri[2];
}
else if (copy_v[i] == "*" && maxPri < pri[3])
{
pos = i;
maxPri = pri[3];
}
}
long long res = 0; // 이것 int가 아닌 long long으로
if (copy_v[pos] == "+")
res = stoll(copy_v[pos - 1]) + stoll(copy_v[pos + 1]);
else if (copy_v[pos] == "-")
res = stoll(copy_v[pos - 1]) - stoll(copy_v[pos + 1]);
else
res = stoll(copy_v[pos - 1]) * stoll(copy_v[pos + 1]);
copy_v.erase(copy_v.begin() + (pos - 1), copy_v.begin() + (pos + 2));
copy_v.insert(copy_v.begin() + (pos - 1), to_string(res));
}
if (stoll(copy_v[0]) < 0)
copy_v[0].erase(copy_v[0].begin());
ans = max(ans, stoll(copy_v[0]));
return;
}
3개의 연산자에 대해 우선순위가 매겨졌다면
우선순위에 따라 식을 계산한다.
이때 우선순위가 제일 큰 연산자의 위치를 pos로 기록한다.
그리고 그 연산자의 종류에 맞춰 pos-1과 pos+1의 수를 연산하여 그 자리에 삽입한다.
이는 수 1개만 남을때까지 반복한다.
만약 마지막 1개의 수가 음수일 경우 부호를 떼준다.
for (int i = 1; i < 4; i++)
{
if (visit[i] == false)
{
visit[i] = true;
pri[idx] = i;
solve(idx + 1, cnt + 1);
visit[i] = false;
}
}
우선순위를 매기는 코드이다.
풀면서 주의할 부분
v.push_back(to_string('@'));
v.push_back("@");
v.push_back("1");
v.push_back(to_string('1'));
서로 다른게 들어간다...
"@"은 벡터에 @가 그대로 들어가지만
"to_string('@')"는 10진수 64로 들어간다...
벡터가 비었을때 아래의 코드에서 에러가 나더라...
vv.insert(vv.begin()+1-1, 5); // 이러면 iterator 에러가 뜬다..
vv.insert(vv.begin()+(1-1), 5); // 묶어주면 또 안뜸...
연산 순서 때문에 그런 것 같은데 다음부터 따로 묶어줘야겠다.
long long res = 0; // 이것 int가 아닌 long long으로
중간중간 연산 결과를 저장하는 변수를 int로 해버릴 뻔했다.
아마 int로 하면 중간에 오버플로우가 일어날 것이다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 최댓값과 최솟값 C++ 풀이 (0) | 2022.09.21 |
---|---|
[프로그래머스] 튜플 C++ 풀이 (0) | 2022.08.04 |
[프로그래머스] 거리두기 확인하기 C++ 풀이 (0) | 2022.07.31 |
[프로그래머스] 뉴스 클러스터링 C++ 풀이 (0) | 2022.07.28 |
[프로그래머스] 괄호 변환 C++ 풀이 (0) | 2022.07.26 |
Comments