#include <iostream>
#include <string>
using namespace std;
string a;
int n;
bool isNumber(char input) {
return ('0' <= input && input <= '9');
}
// 숫자와 다음 위치를 반환.
// 마지막 숫자라면 그 숫자와 -1을 반환
pair<int,int> extractNumber(int start) {
string ret = "";
while (isNumber(a[start])) {
ret += a[start];
start++;
}
if (start == n) return make_pair(stoi(ret), -1);
return make_pair(stoi(ret), start);
}
int main() {
cin >> a;
n = a.size();
bool isMinus = false;
int index = 0;
int ret = 0;
while (true) {
pair<int,int> next = extractNumber(index);
index = next.second; // 다음 위치로 이동
if (isMinus == true){
ret -= next.first;
if (next.second != -1 && a[index] == '-')
isMinus = false;
}
else{
ret += next.first;
if (next.second != -1 && a[index] == '-')
isMinus = true;
}
index++;
if (next.second == -1) break;
}
cout << ret << endl;
return 0;
}
마이너스가 나오면 그 뒤에 나오는 숫자를 최대로 만든다. 즉 그 뒤에 -가 나오기 전까지 괄호로 묶는다. (1) 주어진 입력에서 숫자를 뽑는다. (2) 숫자 뒤에 오는 것이 마이너스면 마이너스임을 저장한다. (isMinus = 1) (3) 마이너스가 나올 때까지 나오는 숫자를 모두 더한다. (4) 마이너스가 나오면, 지금까지 더한 숫자를 처음 구한 숫자와 빼고, isMinus를 0으로 바꾼다. (5) isMinus가 0인 동안은 마이너스가 나올 때까지 나오는 숫자를 모두 더한다.
이 논리대로 풀었으나 , 10-5-5-9와 같이 마이너스가 연속해서 나오는 경우 isMinus가 true가 false가 되어서 두번째 5는 그냥 더해지는 문제가 있었다.
해설
백준님은 여기서 부호와 숫자가 번갈아 나온다는 점을 이용해서, 벡터에 num과 sign을 한꺼번에 정리해놓고 isMinus부호에 따라 더하고, 빼는 것을 반복하였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string s; cin >> s;
vector<int> num, sign;
bool isMinus = false;
int cur = 0;
sign.push_back(1);
for (int i = 0; i < s.size(); i++) {
if (s[i] == '+' || s[i] == '-') {
if (s[i] == '+')
sign.push_back(1);
else
sign.push_back(-1);
num.push_back(cur);
cur = 0;
}
else {
cur = cur * 10 + (s[i] - '0');
}
}
num.push_back(cur);
int ret = 0;
for (int i = 0; i < num.size(); i++) {
if (sign[i] == -1)
isMinus= true;
if (isMinus)
ret -= num[i];
else
ret += num[i];
}
cout << ret << endl;
return 0;
}
내가 여기서 띠용했던 부분은 isMinus를 다시 false로 되돌려 놓는 코드가 없다는 것이었다. 한 번 마이너스가 나오면 그 뒤에 것은 더할 이유가 없다. 마이너스가 나온 상태라면 그 뒤에것은 +이든 -이든 계속 빼면 되는 것이었다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
bool cmp(int num1, int num2) {
return num1 > num2; // 내림차순 정렬
}
int main() {
cin >> n;
vector<int> numbers(n);
for (int i = 0; i < n; i++)
cin >> numbers[i];
sort(numbers.begin(), numbers.end(), cmp);
int index = 0;
vector<int> d;
while (index + 1 < n && numbers[index + 1] > 1) {
d.push_back(numbers[index] * numbers[index + 1]);
index += 2;
}
// 제일 마지막에 있는 것이 음수라면 0과 곱하고 지워준다.
if (numbers.back() < 0 && find(numbers.begin(), numbers.end(), 0) != numbers.end())
numbers.pop_back();
int ret = 0;
for (int i = 0; i < d.size(); i++)
ret += d[i];
for (int i = index; i < numbers.size(); i++)
ret += numbers[i];
cout << ret << endl;
return 0;
}
(1) 완전 탐색으로 구현하려면 50P25의 시간복잡도가 걸린다. (엄청 큰 수) (2) 각 수는 묶거나, 묶지 않으므로 가장 큰 수끼리 묶는 것을 우선으로 하며 0과 1은 묶이지 않는다. 만약 음수가 있다면, 가장 작은 음수와 0을 곱한다.
여기에 추가해야할 조건은, 음수끼리 곱했을 때 양수가 된다는 것이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
bool cmp(int n1, int n2) {
return n1 > n2;
}
int main() {
cin >> n;
vector<int> pos, neg;
for (int i = 0; i < n; i++) {
int num; cin >> num;
if (num > 0) pos.push_back(num);
else neg.push_back(num);
}
vector<int> tied;
// 양수
int index_pos = 0;
sort(pos.begin(), pos.end(), cmp); // 내림차순 정렬
int u = pos.size();
while (index_pos < u - 1 && pos[index_pos + 1] > 1) {
tied.push_back(pos[index_pos] * pos[index_pos + 1]);
index_pos += 2;
}
for (int i = index_pos; i < pos.size(); i++)
tied.push_back(pos[i]);
// 음수
int index_neg = 0;
int v = neg.size();
sort(neg.begin(), neg.end()); // -3, -2, -1 // 오름차순 정렬
while (index_neg < v - 1) {
tied.push_back(neg[index_neg] * neg[index_neg + 1]);
index_neg += 2;
}
for (int i = index_neg; i < neg.size(); i++)
tied.push_back(neg[i]);
int ret = 0;
for (int i = 0; i < tied.size(); i++)
ret += tied[i];
cout << ret << endl;
return 0;
}
이렇게 양수 음수 함께 처리해서 완성하였다.