백준 1541번: 잃어버린 괄호

gim-hangil·2022년 4월 4일
0

문제 풀이

목록 보기
2/7

지금 풀어보기

📝 문제 읽기

덧셈과 뺄셈으로 이루어진 식이 문자열로 주어지고, 자유롭게 괄호를 쳐서 만들 수 있는 최솟값을 출력하면된다.

💡 전략 수립

어떤 식이 있을 때, 어떻게 최솟값을 만들지에 대한 고민이 필요하다. 생각보다 간단하니 잠깐만 생각해보고 읽어나가자.

먼저 연속해서 두 개의 연산자가 나타나지 않는다는 조건에 의해 -(-12) 와 같은 형태는 나타나지 않음을 알 수 있다. 그러면 주어질 식은 음이 아닌 양수를 더하거나 빼는 식이 되는데, 자유롭게 괄호를 쳐서 최대한 많이 뺄셈을 수행하면 최솟값이 나오게 된다.

최대한 많이 뺄셈을 수행하는 방법은 - ( 12 + 13 + 5 ) - ( 3 + 2 + 11 ) 처럼 덧셈을 모두 묶어서 한번에 빼는 것이고, 이 방법을 통해 첫 뺄셈 기호가 등장한 이후의 숫자는 모두 뺄 수 있다.

즉, 처음 등장하는 뺄셈 기호를 기준으로 그 앞의 모든 수를 더하고, 그 뒤의 모든 수를 뺀 값을 출력하는 문제가 된다.

✨ 구현

먼저 연산자가 아닐 경우에는 숫자를 수로 바꾸어야 한다.

for (char c : equation) {
	if (c != '+' && c != '-') v = v * 10 + c - '0';
}

그리고, 연산자라면 아래와 같은 방식으로 연산을 수행한다.

int sign = 1, v = 0, sum = 0;
for (char c : equation) {
	if (c != '+' && c != '-') {
    	v = v * 10 + c - '0';
        continue;
    }
 	sum += v * sign;
    v = 0;
    if (c == '-') sign = -1;
}

이렇게 하면 연산자가 등장해야 연산을 수행하는데, 식의 끝은 연산자로 끝나지 않는다. 그러므로 반복이 끝난 후 남은 v 를 더해 출력해주어야 한다.

0개의 댓글