[백준/C++] 잃어버린 괄호 풀이 1541번 /그리디/알고리즘/코딩테스트 - (1)

백준 1541번 잃어버린 괄호  

 

사실 그리디는 말그대로 욕심쟁이 알고리즘이라고, 매번 선택에 있어서 가장 최적의 답을 고르는 알고리즘입니다. 우리가 최적이라고 아니깐 이걸 쓰는거지 만약에 예외 테스트가 존재할 시 망할 수도 있는 것이죠.

 

그래서, 점화식을 잘 세우고 접근을 해야합니다. 

 

이 문제를 봤을 때 괄호를 쳐서 최소의 숫자를 도출해내는 것이 요구 결과입니다.

어떻게해야 최소가 된다고 하는지 유심히 봤을 때 뒤에 - 마이너스가 나오는 순간부터 다 빼주면 최소가 나오는 결과에 도달 할 수 있습니다. 

 

또 다른 문제 조건은 string으로 한번에 받아서 문자를 숫자로 처리해야한다는 것인데요. 그래서 이부분에서는 STL 함수인 stoi 함수를 썼습니다. 이 함수는 string을 int형으로 바꿔주는 함수라 꼭 기억하는 것이 좋습니다. 그래서 아스키코드로 0 ~ 9까지 들어오면 새로운 string 문자열로 할당해주고, 이 문자열을 int형으로 바꿔서 결국에는 숫자로 쓸 수 있게 만들었죠. 

---

1541 전체 코드 

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

string str;
string sta[50];
int main() {


	cin >> str;
	int num = 0;
	int minu = 0;
	for (int i = 0; i < str.size(); i++) {
		if (int(str[i]) >= 48 && int(str[i]) <= 57) {
			sta[num] += str[i];
		}
		else if (str[i] == '-') {
			//cout << "? " << '\n';
			num++;
			 
			if(minu == 0) minu = num;
			//cout  << num << "\n";
			//cout << "minu : " << minu << "\n";
		}
		else if (str[i] == '+') {
			num++;
		}
	}
	//cout << str[2] << '\n';
	int result = 0;
	for (int i = 0; i < minu; i++) {
		int ex = stoi(sta[i]);
		result += ex;
	}
	if (minu == 0) {
		for (int i = 0; i <= num; i++) {
			int ex = stoi(sta[i]);
			result += ex;
		}
	}
	for (int i = minu; i <= num; i++) {
		if (minu == 0) break;
		int ex = stoi(sta[i]);
		result -= ex;
	}
	//cout << minu << '\n';
	cout << result;
}