본문 바로가기

백준

백준1541 - 잃어버린 괄호

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

 

1541번: 잃어버린 괄호

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

www.acmicpc.net

그리디 문제 중 쉬운 편에 속했다.

0~9사이의 숫자와 -와 +가 임의로 주어졌을 때 괄호를 이용하여 최솟값을 찾는 문제이다.

더하기를 더하기끼리 최대한 묶은 후 뺄셈을 해주면 되는 문제다.

예시를 들어 설명을 하자면 다음과 같다.

1. a - b + c - d + e 인 경우

a - (b + c) - (d + e) = a - b - c - d - e

2. a + b - c + d + e인 경우

a + b - (c + d + e) = a + b - c - d - e

3. a + b - c - d + e + f - g인 경우

a + b - c - (d + e + f) - g = a + b - c - d - e - f - g

눈치 챘는지 모르겠지만 뺄셈기호 뒤에 덧셈기호들은 모두 다 뻴셈으로 변환 할 수 있다.

따라서 뺄셈기호전에 덧셈들은 모두 다 더한 후 나머지 숫자를 빼주면 된다.

 

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


int main() {
	string s; //수식을 입력할 변수
	string num; //수식 안에 숫자를 저장할 변수
	queue<int> q; //숫자를 넣을 공간
	int ans = 0; //답을 출력할 변수


    //수식을 입력하고 숫자들을 모두 찾아서 큐 안에 넣어준다.
	cin >> s;
	for (unsigned int i = 0; i < s.size(); i++) {
		if ('0' <= s[i] && s[i] <= '9') { //숫자인 경우
			num = num + s[i];
		}
		else { //숫자가 아닌 경우
			q.push(stoi(num)); //숫자를 큐에 넣는다.
			num.clear(); //숫자를 담을 변수 초기화
		}
		if (i == s.size() - 1) { //식에 마지막 숫자이면
			q.push(stoi(num)); //숫자를 큐에 넣는다.
			num.clear(); //숫자를 담을 변수 초기화
		}
	}


	ans = q.front(); //우선 첫번째 수를 ans안에 넣는다. (계산을 첫번째 숫자부터 하기 위하여)
	q.pop(); //큐에 첫번째 원소를 팝
	for (unsigned int i = 0; i < s.size(); i++) { //수식에서 -기호를 만나기 전 모든 +기호를 더하는 과정
		if (s[i] == '+') { //덧셈이면
			ans = ans + q.front(); //큐에 첫번째 원소를 ans에 더해준다.
			q.pop(); //큐에 첫번째 원소를 팝
		}
		else if(s[i] == '-') { //뺄셈이면
			break; //탈출
		}
	}
    
    
	while (q.size()) { //큐가 빌 때까지
		ans = ans - q.front(); //큐 안에 모든 원소를 빼준다.
		q.pop();
	}
    
    
	cout << ans;
}

'백준' 카테고리의 다른 글

백준2870 - 수학숙제  (0) 2019.06.19
백준17213 - 과일서리  (0) 2019.06.19
백준11729 - 하노이 탑 이동 순서  (0) 2019.06.11
백준2012 - 등수 매기기  (0) 2019.06.11
백준1389 - 케빈 베이컨의 6단계 법칙  (1) 2019.06.11