잃어버린 괄호 문제
1541번: 잃어버린 괄호
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다
www.acmicpc.net
소스코드
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string s,tmp="";
int result = 0;
bool check = false;
cin >> s;
int size = s.size();
for (int i = 0; i <= size; i++) {
if (s[i] == '-'||s[i]=='+'||s[i]=='\0') {
if (check)
result -= stoi(tmp);
else
result += stoi(tmp);
tmp = "";
if (s[i] == '-')check = true;
continue;
}
tmp += s[i];
}
cout << result;
}해결방법
문자열을 어떻게 처리할 수 있는가..
어떻게 문제를 풀어나가는가 하면 +기호가 나오면 그냥 계속 더해줍니다. 그러다가 -마이너스 기호를 만나게 되면 그 뒤로 어떤 연산자가 나오던간에 그냥 계속 빼주면 그게 가장 작은 숫자가 됩니다.
55-50+40
프로그램 로직상은 55를 만나서 result에 저장해줍니다. 그러다 -마이너스를 만나 55-50-40을 해줍니다.
이게 무슨의미냐하면 55-(50+40)이렇게 괄호를 쳣다고 가정하면, 분배법칙에 의해 55-50-40으로 바뀔 수 있습니다.
괄호 앞에 마이너스가 붙게되면 그 이후의 숫자들은 그냥 계속 뺀다고 생각하면 쉽게 해결할 수 있습니다.
'Algorithm > greedy' 카테고리의 다른 글
| [백준] 알고리즘 11399번 - ATM 문제 (0) | 2021.02.08 |
|---|---|
| [백준] 알고리즘 11047번 - 동전 0 문제 (0) | 2021.02.07 |
| [백준] 알고리즘 5585번 - 거스름돈 문제 (0) | 2021.02.06 |
| [알고리즘 문제] 숫자 카드 게임 (0) | 2020.10.30 |
| [알고리즘 문제] - C++ 그리디 알고리즘 문제 : 큰 수의 법칙 (0) | 2020.10.29 |
