백준 잃어버린 괄호 1541 C++

1541: 잃어버린 괄호

+와 - 연산자만이 주어졌을 때 주어진 식에 괄호를 처서 최소값을 출력하는 문제.

모든 +식에 괄호를 치고 -를 나중에 계산하는 방식으로 최소값을 만들 수 있다.

문제 풀이를 두 파트로 나누어 진행하였다.
1. string으로 주어지는 수식 분해
2. 숫자 계산

1. string으로 주어지는 수식 분해

• string을 처음부터 끝까지 탐색하면서 한 글자씩 tmpnum이라는 string형 변수에 저장
• 탐색 중 연산자를 만나면
  1. 연산자는 opr이라는 배열에 저장
  2. tmpnum에 저장된 string을 stoi 함수를 이용해 int로 변환, num 배열에 저장
  3. tmpnum을 공백으로 초기화
• 연산자를 만나야 숫자가 저장되기 때문에 마지막 숫자는 저장되지 않음
• 따라서 string 탐색이 끝나면 tmpnum에 저장된 마지막 숫자를 num 배열에 추가함

2. 숫자 계산

• 스택을 사용하여 숫자를 계산
• 첫 번째 숫자는 stack에 push
• opr 배열을 탐색하는 반복문을 실행
• 연산자가 +이면 stack의 top에 있는 숫자와 num[i+1] 숫자를 더함
• 연산자가 -이면 num[i+1]을 stack에 push
• opr배열 탐색이 끝나면 stack에 있는 stack size -1 개의 숫자를 pop해서 0에서 뺌
• stack 가장 아래에 있는 값은 항상 양수이기 때문에 앞에서 뺀 값에 더해주며 출력

간단한 문제인데 마지막 뺄셈 과정의 반복문에 stack.size()를 변수로 사용하는 실수를 해서, 생각보다 오래 걸렸음..

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

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

	int idx = 0;
	int num[101] = { 0, };
	string tmpnum = "";
	char opr[51] = { 0, };

	for (int i = 0; i < s.length(); i++) {
		if (s[i] == '+') { opr[idx] = '+'; num[idx] = stoi(tmpnum); tmpnum = ""; }
		else if (s[i] == '-') { opr[idx] = '-'; num[idx] = stoi(tmpnum); tmpnum = ""; }
		else { tmpnum += s[i]; continue; }
		idx++;
	}
	num[idx] = stoi(tmpnum);

	stack<int> stack;
	int tmp = 0;
	stack.push(num[0]);

	int i = 0;
	while (opr[i] != 0) {
		if (opr[i] == '+') {
			tmp = stack.top() + num[i+1];
			stack.pop();
			stack.push(tmp);
		}
		else if (opr[i] == '-') {
			stack.push(num[i + 1]);
		}
		i++;
	}
	
	int sum=0;
	int stack_size = stack.size();
	for (int j = 0; j < stack_size -1; j++) {
		sum -= stack.top();
		stack.pop();
	}
	
	cout << (sum + stack.top());
		
}