[C++] 백준 1541: 잃어버린 괄호

문제

[C++] 백준 1541: 잃어버린 괄호 SILVER 2
https://www.acmicpc.net/problem/1541

 

---

 

접근 방법

이 문제는 주어진 식에 괄호를 적절히 쳐서 결과 값을 최소로 만드는 문제다.
핵심 아이디어는 정말 단순하다.

한 번 - 가 등장한 이후에는, 그 뒤에 나오는 모든 수를 한 덩어리로 묶어서 한 번에 빼면 전체 값을 최소로 만들 수 있다.

 

예를 들어,

• 55-50+40 이라면
  → 55-(50+40) 으로 묶는 게 최솟값

즉, 첫 번째 -를 기준으로 식을 나누고,

• 첫 번째 덩어리는 그대로 더하고
• 두 번째 덩어리부터는 “+로 묶인 값들을 모두 더한 뒤” 통째로 빼면 된다.

 

상세 아이디어

1. split 함수로 문자열 자르기

먼저, 문자열을 특정 문자 기준으로 잘라주는 split 함수를 만들었다.

vector<string> split(string str, char ch)  // ch를 기준으로 문자열 분리
{
	vector<string> result;
	
	stringstream ss(str);
	string splitstr = "";

	while (getline(ss, splitstr, ch))
		result.push_back(splitstr);

	return result;
}

• stringstream ss(str)의 의미:
  문자열 str을 입력 스트림처럼 다루겠다.
  즉, cin처럼 읽을 수 있는 대상으로 만들겠다.
• while (getline(ss, splitstr, ch))의 의미:
  ss에서 문자 ch를 만날 때까지 문자열을 읽어서, 그 결과를 splitstr에 저장한다.

2. getSum으로 +로 묶인 구간 합 구하기

getSum은 "3+4+5" 같은 문자열을 받아서
+를 기준으로 나눈 숫자들을 전부 더한 값을 반환한다.

int getSum(string str)
{
	vector<string> vect = split(str, '+');

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

	return sum;
}

 

• 내부에서 다시 split(str, '+') 를 사용
• 잘린 문자열들을 stoi로 정수 변환 후 모두 더함

3. main 함수

• 전체 식을 - 기준으로 먼저 쪼갠다.
• 첫 번째 조각은 아직 -를 만나기 전이므로, 그냥 더하는 부분이다.
• 그 이후의 조각들은 모두 빼준다.

 

구현 시 주의할 점

• - 기준으로 한 번 나누고, 각 덩어리에서 다시 +를 기준으로 나누는 구조이기 때문에
  첫 번째 덩어리는 더하고, 그 이후 덩어리들은 전부 빼야 한다는 규칙을 꼭 지켜야 한다.

 

---

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

vector<string> split(string str, char ch)  // ch를 기준으로 문자열 분리
{
	vector<string> result;
	
	stringstream ss(str);
	string splitstr = "";

	while (getline(ss, splitstr, ch))
		result.push_back(splitstr);

	return result;
}
int getSum(string str)
{
	vector<string> vect = split(str, '+');

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

	return sum;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str = "";
	cin >> str;

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

	int sum = 0;
	for (int i = 0; i < vect.size(); i++)
	{
		int ret = getSum(vect[i]);

		if (i == 0)
			sum += ret;
		else
			sum -= ret;
	}
	cout << sum;

	return 0;
}