[BOJ 1541] 백준 잃어버린 괄호 풀이 - C++

사용언어 :  C++

 

 

문제풀이

---

<알고리즘 구하기>

(1) 55 - 50 + 40 

=> 55 - (50+40) = -35

(2) 40+20 - 60+30

=> 40+20 - (60+30) = -30

(3) 40-20+30+30

=> 40 - (20+30+30) = -40 

 

=> '-' 빼기 연산자가 나오면 그 뒤 연산식을 괄호로 묶는다. 

=> 즉, - 연산자가 하나라도 나오면 그 뒤의 피연산자들은 빼기 연산을 진행한다 

---

* 변수 설정

string order; //입력 받는 식
vector<int> operands; // 숫자 저장
string tmp; //숫자 값 임의로 저장
int plus_cnt=0; //더하기 몇 번 해야하는지 
bool minus_flag = false; //- 연산자 나왔는지

 

(1) 연산자, 피연산자 구분하기 (피연산자는 vector에 저장)

+ '-' 빼기 연산자가 언제 나오는지 확인하기 (빼기 연산자가 안나왔으면 '+' 더하기 연산자 카운트 증가)

  	cin >> order; 
	for (int i = 0; i < order.size(); i++) {
    
    	//숫자 일 때 (피연산자) 
		if (order[i] != '-' && order[i] != '+') {
			tmp = tmp + order[i];
			continue; //연산자일 때만 operands vector에 값 넣어주기 위해서 
		}
        
        // - 일 때 => minus_flag=true 로 바꿔주기
		else if (order[i] == '-') {
			minus_flag = true;
		}
        
        // + 일 때 => minus_flag가 false면 더하기 카운트 증가
		else 
			if (minus_flag == false) {
				plus_cnt++;
			}
		operands.push_back(stoi(tmp));
		tmp = "";
		
	}
	operands.push_back(stoi(tmp)); //마지막은 항상 피연산자이기 때문에 남은 숫자 operands vector에 넣어주기

 

(2) plus_cnt 갯수를 기준으로 식 계산하기

int answer = operands[0]; //맨 처음 값은 항상 양수
	for (int i = 1; i < operands.size(); i++) {
		if (plus_cnt>0) { //plus_cnt 갯수만큼만 answer에 숫자 더해주기
			answer += operands[i];
		}
		else
			answer -= operands[i];
		plus_cnt--;
	}

	cout << answer;

 

 

전체코드

 

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

string order;
vector<int> operands;
string tmp;
int plus_cnt=0;
bool minus_flag = false;

int main() {
	cin >> order; 

	for (int i = 0; i < order.size(); i++) {
		if (order[i] != '-' && order[i] != '+') {
			tmp = tmp + order[i];
			continue;
		}
		else if (order[i] == '-') {
			minus_flag = true;
		}
		else 
			if (minus_flag == false) { 
				plus_cnt++;
			}
			operands.push_back(stoi(tmp));
			tmp = "";
		
	}
	operands.push_back(stoi(tmp));
	int answer = operands[0];
	for (int i = 1; i < operands.size(); i++) {
		if (plus_cnt>0) {
			answer += operands[i];
		}
		else
			answer -= operands[i];
		plus_cnt--;
	}

	cout << answer;
}

 

 

 

총평

코드가 조금 지저분한 것 같기도 하고,,, 조금 더 간단한 방법이 있을텐데 생각이 안난다. 별개로 식이 괄호를 어떻게 묶었을 때 최소가 되는지 로직을 구하는 데 어려움이 있었다. 처음엔 그냥 하나하나 계산을 한 후에 최솟값을 구하려했다. 그렇게 생각하니까 당연히 코드 짜기 어려웠다..ㅎㅎ 하나하나 계산해서 최솟값을 구하는게 아니라 최솟값이 될 조건을 수학적으로 생각해내야 해서 허무하기도 하면서 하나 더 배워가는 느낌도 있었다.

---

문제 출처

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

1541번: 잃어버린 괄호