백준 1541 - 잃어버린 괄호(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

문자열과 그리디 알고리즘을 사용하여 푸는 문제였습니다.

문제 조건

출력 예시

크게 2가지의 과정을 통해 문제를 풀면 됩니다.

1. 문자열을 숫자와 수식으로 변경해 저장하기

2. 숫자를 뺄 경우 뺄 수 있는 최댓값을 구하기

 

 

1. 문자열을 숫자와 수식으로 변경하기

void get_number() {
	string now_number;
	for (int i = 0; i < formula.size(); i++) {
		if (formula[i] == '+') {
			num_plus++;
			Operator.push_back(1);
			number.push_back(stoi(now_number));
			now_number = '0';
		}
		else if (formula[i] == '-') {
			num_minus++;
			Operator.push_back(-1);
			number.push_back(stoi(now_number));
			now_number = '0';
		}
		else {
			now_number += formula[i];
		}
	}
	if (now_number != "0") number.push_back(stoi(now_number));
}

먼저 + 와 - 의 경우 각각 1과 -1로 저장했습니다. (Operator 배열)

수식이 나오기 전까지 문자만 계속 나왔을 경우에는 해당 문자들을 합친뒤, 수식이 나왔을 때 저장해줬습니다.

 

문자열 탐색이 끝난 뒤에도 아직 저장되지 않은 수가 있다면 마지막까지 저장해줍니다.

 

 

2. 숫자를 뺄 경우 뺄 수 있는 최댓값 구하기

위와 같은 식이 있을때, 수는 연산자보다 항상 앞에 있는 것을 확인할 수 있습니다.

이때 만들 수 있는 값의 최솟값은 2번째 그림일 경우입니다.

 

따라서 뺼 수 있는 최댓값을 구하는 방법은 '-' 연산자를 만났을 때, 다음 '-' 연산자가 나올때까지 수들을 계속 더해줍니다.

void calculate_minus(int x) {
	int start = x + 1;
	int sum = 0;
	while (1) {
		sum += number[start];
		if (start >= Operator.size()) break;
		if (Operator[start] == -1) break;
		start++;
	}
	max_minus.push_back({ {x, start}, sum });
}

'-' 연산의 시작점과 끝점을 저장해준뒤 해당 수열에서의 합을 저장해줍니다.

시작점과 끝점은 수열의 최솟값을 구할 때 연산 위치를 바꾸는 것에 사용합니다.

 

 

 

1번과 2번 과정이 모두 끝났다면 2가지 경우로 답을 나눠야합니다.

1. '-' 연산자가 없을 경우 -> 모든 수를 더해줍니다.

2. '-' 연산자가 있을 경우 -> 빼야할 수를 모두 구해줬기에 순서대로 계산합니다.

위의 그림을 봤을때, 수열을 계산하는 방법은 맨 앞의 수를 저장한 뒤, 연산자에 따라 수를 계산해주면 됨을 알 수 있습니다.

 

 

문제 접근 방법

1. 문자열에서 수와 연산자를 구한다.

2. '-' 연산자의 갯수에 따라 답을 출력한다.

    2-1. '-' 연산자가 없을 경우 -> 모든 수를 더해준다.

    2-2. '-' 연산자가 있을 경우 -> 뺄 수 있는 수의 값을 모두 구한뒤 계산한다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <map>

using namespace std;

string formula;
int num_plus, num_minus;
vector<int> number;
vector<int> Operator; // plus = 1 , minus = -1
vector<pair<pair<int, int>, int>> max_minus;
int Start, End, maxi = 0;

void get_number() {
	string now_number;
	for (int i = 0; i < formula.size(); i++) {
		if (formula[i] == '+') {
			num_plus++;
			Operator.push_back(1);
			number.push_back(stoi(now_number));
			now_number = '0';
		}
		else if (formula[i] == '-') {
			num_minus++;
			Operator.push_back(-1);
			number.push_back(stoi(now_number));
			now_number = '0';
		}
		else {
			now_number += formula[i];
		}
	}
	if (now_number != "0") number.push_back(stoi(now_number));
}

void calculate_minus(int x) {
	int start = x + 1;
	int sum = 0;
	while (1) {
		sum += number[start];
		if (start >= Operator.size()) break;
		if (Operator[start] == -1) break;
		start++;
	}
	max_minus.push_back({ {x, start}, sum });
}

int get_ans() {
	int ans = number[0];
	int cnt = 0;
	for (int i = 0; i < number.size() - 1; i++) {
		if (cnt < max_minus.size()) {
			if (i == max_minus[cnt].first.first) {
				ans -= max_minus[cnt].second;
				i = max_minus[cnt].first.second - 1;
				cnt++;
				continue;
			}
		}
		if (Operator[i] == 1) {
			ans += number[i + 1];
		}
		else {
			ans -= number[i + 1];
		}
	}
	return ans;
}

void solve() {
	int ans = 0;
	get_number();
	if (num_minus == 0) {
		for (int i = 0; i < number.size(); i++) {
			ans += number[i];
		}
		cout << ans;
	}
	else {
		for (int i = 0; i < Operator.size(); i++) {
			if (Operator[i] == -1) {
				calculate_minus(i);
			}
		}
		cout << get_ans();

	}
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> formula;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요