그리디 알고리즘 - 최솟값을 만드는 괄호 배치 찾기

이번 문제는 문제에 대한 아이디어도 중요하지만 사용할 함수를 잘 파악하는 것이 매우 중요하다.

 

<문제>

백준 - 1541: 최솟값을 만드는 괄호 배치 찾기

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

1541번: 잃어버린 괄호

 

괄호를 적절히 배치해 식의 값을 최소로 만드는 프로그램을 작성하는 문제이다.

 

예)

100-42+50+74-30+29-45+43+11

→ 100 - (42+50+74) - (30+29) - (45+43+11)

 

<문제 해결>

split 함수와 getline 함수를 이용해 풀어야하는 문제이다.

 

▶ 문자열 split 참고 코드와 내용

https://www.lifencoding.com/language/22?p=1 

[C++] string타입 문자열을 split하기

 

1. string으로 식을 입력받은 후 입력받은 식을 '-' 기준으로 split해야 한다. 또한, split한 문자열을 '+' 기준으로 한 번 더 split해 접근해야 한다.

 

2. 1번의 과정을 통해 얻은 '+'로 이루어진 식을 하나의 그룹으로 만들어 그 그룹 안에 숫자들을 모두 합(hap 변수)해 준 후 최종 답을 출력할 변수인 cal에 빼준다.

 

3. 2번의 과정을 '-' 기준으로 split한 그룹에 다 적용할 때까지 반복한다.

 

Corner case 정리)

1. split 함수와 getline 함수를 사용자 정의 함수에서 잘 이용해야 한다.

 

<슈도 코드>

str_all = 입력할 식
cal = 최종 값
	cin >> str_all;

	vector <string> str = split(str_all, '-'); 

	for (i = 0; i < str.size(); i++) {
		int hap = Sum(str[i]);

		if (i == 0) { // 입력할 때 가장 첫 번째 수는 cal에 더해주기
			cal = cal + hap;
		}

		else { // cal에 더하기로 이루어진 그룹 숫자들의 합 빼기
			cal = cal - hap;
		}
	}

	cout << cal;
}

vector <string> split(분리할 문자열, 특정 기준으로 분리할 문자) { // 문자열 특정 구분자로 잘라 벡터에 저장하는 함수
	vector<string> result;
	stringstream mystream(input);
	string splitdata;

	while (getline(mystream, splitdata, delimiter)) { // getline함수: 지정한 delimiter를 만나기 전까지 모든 문자를 읽어서 splitdata에 저장
		result.push_back(splitdata);
	}
	return result;
}

int Sum(+로만 이루어진 문자열) { // +로만 이루어진 그룹의 숫자들 모두 더하기
	int sum = 0;
	vector <string> str_part = split(s, '+');

	for (i = 0; i < str_part.size(); i++) {
		sum += stoi(str_part[i]);
	}

	return sum;
}

 

<전체 코드>

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
vector <string> split(string input, char delimiter);
int Sum(string s);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str_all;
	int cal = 0;
	cin >> str_all;

	vector <string> str = split(str_all, '-');

	for (int i = 0; i < str.size(); i++) {
		int hap = Sum(str[i]);

		if (i == 0) { // 입력할 때 가장 첫 번째 수는 cal에 더해주기
			cal = cal + hap;
		}

		else { // cal에 더하기로 이루어진 그룹 숫자들의 합 빼기
			cal = cal - hap;
		}
	}

	cout << cal;
}

vector <string> split(string input, char delimiter) { // 문자열 특정 구분자로 잘라 벡터에 저장하는 함수
	vector<string> result;
	stringstream mystream(input);
	string splitdata;

	while (getline(mystream, splitdata, delimiter)) { // getline함수: 지정한 delimiter를 만나기 전까지 모든 문자를 읽어서 splitdata에 저장
		result.push_back(splitdata);
	}
	return result;
}

int Sum(string s) { // +로만 이루어진 그룹의 숫자들 모두 더하기
	int sum = 0;
	vector <string> str_part = split(s, '+');

	for (int i = 0; i < str_part.size(); i++) {
		sum += stoi(str_part[i]);
	}

	return sum;
}