Problem 문제풀이
나처럼 실수 많고 성격 급한 사람에게 정말 좋은 문제이다. 정답을 맞추고
바로 다시 풀었는데도 7번 틀릴 정도로 실수 요소가 많은 문제이다. 그냥 내가 성격이 급한읍읍
문제 풀이를 시작하겠다.
전략
-
문제를 매우! 잘! 꼼꼼히! 읽는다.
-
주어진 문자열을 숫자와 연산자로 분리하여 각각 vector에 저장한다.
-
연산자를 순회하면서 괄호를 씌울지 말지 결정한다. (여기서 괄호를 씌울경우 다음 연산자는 괄호를 씌울 수 없다.)
-
연산자를 전부 탐색했으면 왼쪽부터 순서대로 연산한다. 주의하라. *,+,- 전부 우선순위가 같다!
문제를 잘 읽었다면 금방 풀 수 있는 문제이다.
먼저 주어진 문자열을 숫자와 연산자로 분리해보자.
cin >> N >> str;
int prev = 0;
for (int i = 0; i < N; i++)
{
if (str[i] == '+' || str[i] == '-' || str[i] == '*')
{
string tmp = str.substr(prev, i - prev);
num.push_back(stoi(tmp));
op.push_back(str[i]);
prev = i + 1;
}
}
string tmp = str.substr(prev, N - prev);
num.push_back(stoi(tmp));
마지막 두 줄 굉장히 중요하다. 저거 빼먹고 헤매는 경우가 굉장히 많다.
num vector에 숫자가, op vector에 연산자가 잘 들어갔다. 이제 괄호를 씌우는 작업을 진행하자.
void solve(int idx)
{
for (int i = idx; i < op.size(); i++)
{
if (op[i] == '+')
{
op[i] = 'P'; //Plus
solve(i + 2);
op[i] = '+';
}
else if (op[i] == '-')
{
op[i] = 'S'; //Subtract
solve(i + 2);
op[i] = '-';
}
else if (op[i] == '*')
{
op[i] = 'M'; //Multiplication
solve(i + 2);
op[i] = '*';
}
}
괄호를 씌운 연산자는 영어로 표기를 바꾸었다. i가 op.size()보다 커지면
영어로 된 연산자를 먼저 계산하고 그 후에 앞에서부터 차례대로 계산하면 된다.
재귀함수를 부르고 연산자를 원래대로 돌리는 것을 잊지 말자!
vector<int>_num = num;
vector<char>_op = op;
for (int i = 0; i < _op.size(); i++)
{
if (_op[i] == 'P' || _op[i] == 'S' || _op[i] == 'M')
{
if (_op[i] == 'P')
{
_num[i] += _num[i + 1];
}
else if (_op[i] == 'S')
{
_num[i] -= _num[i + 1];
}
else if (_op[i] == 'M')
{
_num[i] *= _num[i + 1];
}
_num.erase(_num.begin() + i + 1);
_op.erase(_op.begin() + i);
i--;
}
}
while (!_op.empty())
{
if (_op[0] == '+')
{
_num[0] += _num[1];
}
else if (_op[0] == '-')
{
_num[0] -= _num[1];
}
else if (_op[0] == '*')
{
_num[0] *= _num[1];
}
_num.erase(_num.begin() + 1);
_op.erase(_op.begin());
}
if (answer < _num.back())
{
answer = _num.back();
}
}
i–를 하지 않아도 정상 동작할 것이다. 그러나 vector를 erase할 경우 i–를 해주는 습관을 들이자.
만약 i–를 하지 않을 경우 erase한 다음 원소는 건너뛰게 되니 주의하자!
여기까지 했으면 다 풀었으니 안심하는 사람이 있을 수 있다. 그러나 이 문제는 결코 안심을 해서는 안 된다.
정답의 범위가 -2^31~2^31인 것을 기억하는가. answer를 0으로 초기화하고 기분좋게 제출을 누른뒤 틀렸습니다를
받는 필자가 겪은 불상사를 겪는 사람은 더이상 없기를 바란다. 추천하는 초기값은 다음과 같다.
answer = (1 << 31);
전체 코드를 남기며 마무리하겠다. Good Luck!
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int N, answer;
string str;
vector<int>num;
vector<char>op;
void solve(int idx);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> str;
int prev = 0;
for (int i = 0; i < N; i++)
{
if (str[i] == '+' || str[i] == '-' || str[i] == '*')
{
string tmp = str.substr(prev, i - prev);
num.push_back(stoi(tmp));
op.push_back(str[i]);
prev = i + 1;
}
}
string tmp = str.substr(prev, N - prev);
num.push_back(stoi(tmp));
answer = (1 << 31);
solve(0);
cout << answer;
return 0;
}
void solve(int idx)
{
for (int i = idx; i < op.size(); i++)
{
if (op[i] == '+')
{
op[i] = 'P'; //Plus
solve(i + 2);
op[i] = '+';
}
else if (op[i] == '-')
{
op[i] = 'S'; //Subtract
solve(i + 2);
op[i] = '-';
}
else if (op[i] == '*')
{
op[i] = 'M'; //Multiplication
solve(i + 2);
op[i] = '*';
}
}
vector<int>_num = num;
vector<char>_op = op;
for (int i = 0; i < _op.size(); i++)
{
if (_op[i] == 'P' || _op[i] == 'S' || _op[i] == 'M')
{
if (_op[i] == 'P')
{
_num[i] += _num[i + 1];
}
else if (_op[i] == 'S')
{
_num[i] -= _num[i + 1];
}
else if (_op[i] == 'M')
{
_num[i] *= _num[i + 1];
}
_num.erase(_num.begin() + i + 1);
_op.erase(_op.begin() + i);
i--;
}
}
while (!_op.empty())
{
if (_op[0] == '+')
{
_num[0] += _num[1];
}
else if (_op[0] == '-')
{
_num[0] -= _num[1];
}
else if (_op[0] == '*')
{
_num[0] *= _num[1];
}
_num.erase(_num.begin() + 1);
_op.erase(_op.begin());
}
if (answer < _num.back())
{
answer = _num.back();
}
}