[알고리즘] 백준 1541번: 잃어버린 괄호 (C++), 경험으로부터 나온 생각과 내 거친 생각과 불안ㅎ..

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

 

이번 문제는 문자열을 통으로 받아서 수와 연산자들을 분리하고, 또 받은 수에 앞이 0이 붙어있을 경우 앞에 0을 제거해주는 작업을 한 뒤 그리디하게 괄호를 붙여주면(논리 작업) 풀리는 문제다. (구현 어려울까봐 미루던 문제)

 

우선 입력을 받고 문자열을 다음과 같은 포인트에서 수로 변환하는 작업을 거친다.

1. 연산자가 나올 때
2. 끝날 때

수를 받고서 예를 들어, "00085"인 경우 앞에 "000"을 제거하고, 수로 변환해주어야 한다. 이 문제는 다음 포스팅의 문자열 합을 구현하는 함수에서 영감을 얻었다.

https://draw-code-boy.tistory.com/77

[알고리즘] 백준 4150번: 피보나치 수 (C++), DP인데 배열을 안 쓴다고?

[문자열 앞 0 제거 함수]

string zeroTrash(string temp) {
	reverse(temp.begin(), temp.end());

	while (temp.back() == '0' && temp.size() > 1) {
		temp.pop_back();
	}

	reverse(temp.begin(), temp.end());

	return temp;
}

while의 조건에서 size가 1인 경우를 남겨둔 이유는 전부 다 pop 해버리면 "0"이라는 숫자가 들어왔을 때는 전부 pop이 되어버리기 때문이다.

 

---

솔루션

솔루션 자체는 문제를 풀고나니 '너무 어렵게 생각했었나'라는 느낌이 들었다.

'-(마이너스)'가 나온 시점부터 모든 수를 다 빼면 된다.

그리고, 0이 나올 때는 부호에 영향을 줄 거 같아서 0이 나올 때는 부호랑 0의 과정을 통째로 날려버렸다.

(실제로는 영향이 없으나 그 전에 떠올랐던 논리를 사용하다가 조금만 바꿔서 문제를 풀어서 크게 상관없는 내용)

 

// 문자열 식을 먼저 수로 변환하는 작업이 필요함

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

string zeroTrash(string temp) {
	reverse(temp.begin(), temp.end());

	while (temp.back() == '0' && temp.size() > 1) {
		temp.pop_back();
	}

	reverse(temp.begin(), temp.end());

	return temp;
}

int main() {
	string value;
	cin >> value;

	vector<int> num; // 숫자
	vector<char> oper; // 연산자

	string temp;
	for (int i = 0; i < value.size(); i++) {
		if (value[i] == '+' || value[i] == '-') {
			zeroTrash(temp);
			num.push_back(stoi(temp));

			oper.push_back(value[i]);
			temp = "";
		}
		else if (i == value.size() - 1) {
			temp += value[i];

			zeroTrash(temp);
			num.push_back(stoi(temp));
			temp = "";
		}
		else {
			temp += value[i];
		}  
	}

	int sum = num[0];
	bool minus = 0;
	for (int i = 1; i < num.size(); i++) {
		if (num[i] == 0) {
			continue;
		}

		if (oper[i - 1] == '-') {
			sum -= num[i];

			if (minus == 0) {
				minus = 1;
			}
		}
		else {
			if (minus == 1) {
				sum -= num[i];
			}
			else {
				sum += num[i];
			}
		}
		//cout << sum << ' ';
	}
	cout << sum;

	return 0;
}