그리디 - 백준 1541번 잃어버린 괄호

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

문제 해석을 못해서 꽤나 애먹었다;; 괄호를 1개만 쳐야하는건지 , 여러개 쳐도 되는건지, 연속해서 나타난다는게 ++ 같은 건지 아니면 1 + 2 + 3 이런식인건지,,,, 테스트케이스도 1개밖에 없고 문제를 이해를 잘 못했다. 

 

👉 결론적으로 괄호는 하나 이상! 여러개 칠 수 있다. 연속해서 연산자가 나오지 않는다는 건 1 ++ 2 같은 게 안된단 뜻

 

IDEA 

1. 어떤 식으로 풀지 고민하기 전에 가장 먼저 입력받은 식을 숫자는 숫자대로, 부호는 부호대로 받아야한다. 

이래서 알고리즘 분류가 문자열,파싱인가보다.

나는 숫자와 부호를 구분해서 각각 num, sign이라는 벡터에 넣어줬다. 

getline을 통해 한줄을 통으로 string 입력받은 후, 인덱스를 잘라가며 보았다.

setence[i]가 숫자라면 우선 temp라는 벡터에 넣어준다. 

부호가 나온 경우가 중요하다.

우선 부호를 sign 벡터에 넣어주고 , temp에 담겨져있던 수들로 숫자를 만든다. ex ) [ 1, 3, 9]

temp 뒤에서부터 하나하나 빼며 10을 계속 곱해준다. ex) 9 + 10 * 3 + 10 *10 * 1

* 수와 숫자는 다르다. 수는 0~9를 얘기하는거고, 숫자는 11, 1, 593등을 얘기하는거다 

 

2. 이게 왜 그리디인지 생각해보아야한다. 언제 최소가 될까?

 ➖ 음의 부호가 나온다면 그 다음 -까지 묶어버리면 최소다 .

예를 들어)  1 - 2 + 3 - 4 + 5 + 6 -7-8 이라면 1- (2 + 3 ) - (4 + 5 + 6) -7 -8 이런식으로 ! 

이걸 수학계산으로 괄호를 풀어서 다시 보면 1- 2- 3 -4 -5 -6 -7 -8 

즉 ,맨 처음 음의 부호  ➖가 나온 이후 숫자는 모두 뺴주면 된다.

 

3. 처음  ➖ 부호가 나올 때까지는 숫자들을 모두 더해준다. 

이후 ➖ 가 나왔다면 그 이후 숫자들은 모두 뺴준다. 

위의 예와 같은 경우

인덱스	0	1	2	3	4	5	6	7
부호	-	+	-	+	+	-	-
숫자	1	2	3	4	5	6	7	8

처음 ➖ 가 나오는 인덱스는 0이다. 

그럼 num[0]까지는 더해준 후 , 이 이후 숫자들은 모두 빼주면 된다. 

CODE

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


int main() {
	string sentence;
	getline(cin, sentence);
	vector<int>temp;
	vector<int>num;
	vector<char>sign;

	//숫자 , 부호 구분해서 벡터에 넣기 
	for (int i = 0; i <= sentence.size(); i++) {
		if (0 <= sentence[i] - '0' && sentence[i] - '0' <= 9) temp.push_back(sentence[i] - '0');
		else { //부호일 경우
			sign.push_back(sentence[i]); //부호 집어넣기
			int sum = 0, ten = 1; //숫자 집어넣기
			while (!temp.empty()) {
				sum += temp.back() * ten;
				temp.pop_back();
				ten *= 10;
			}
			num.push_back(sum);
		}
	}

	// -가 한 번 나오면 그 이후부터는 다 빼기!  괄호로 묶으면 되니까
	int answer = 0 , i;
	for (i = 0; i < sign.size(); i++) {
		answer += num[i];
		if (sign[i] == '-') break;
	}
	for (int j = i + 1; j < num.size(); j++) {
		answer -= num[j];
	}
	printf("%d", answer);
}