[백준-그리디] 잃어버린 괄호 (Java)

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

제한 조건

• 풀이 시간 : 30분
• 시간 제한 : 2초

입력 조건

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

출력 조건

• 첫째 줄에 정답을 출력한다.

예시

입력	출력
55-50+40	-35
10+20+30+40	100
00009-00009	0

풀이

덧셈, 뺄셈 연산식에서 최소값을 만드는 방법은 - 뒤에 오는 +들을 다 묶어주면 된다. 하지만 이 것을 더 단순하게 표현하면 최초에 -가 나온 뒤의 모든 숫자들을 빼버리면 된다는 것이다. 또한 연산식의 길이가 50자 이하이므로 O(N)의 시간 복잡도로 풀이해도 문제가 없다. 그래서 다음과 같이 코드를 작성하기로 했다.

1. 연산식의 char를 순서대로 받아서 +, -가 아니면 StringBuilder에 append한다.
2. +가 나오면 StringBuilder의 값을 Integer로 변환하여 더한다.
3. -가 나오면 flag를 세워 이후의 값들을 모두 뺄 수 있도록 한다.
4. 마지막 값은 숫자이므로 for loop가 끝난 후 StringBuilder의 값을 flag에 맞춰 더하거나 뺀다.

• flag는 -가 최초로 나온 시점을 구별하기 위함

하지만 이 논리는 단순한 것 같지만 실제로 코드를 구현하는 것은 생각보다 어려웠다. 불필요하게 반복되는 로직들이 발생했고, 고려해야하는 경우의 수가 많아져 코드를 작성하는데 애를 먹었다.

다른 사람들의 코드를 보니 split을 활용하여 문제를 풀이하고 있었다. 생각해보니 이 문제는 괄호를 쳐주는 것이 목표고, -를 기준으로 split을 하는 것이 곧 괄호를 쳐주는 것과 같다는 것을 깨달았다. 그래서 다음과 같이 코드를 수정하였다.

1. -를 기준으로 split을 한다.
2. split된 문자열이 empty일 경우, flag를 세우고 다음 문자열로 넘어간다.
3. split된 문자열이 empty가 아닐 경우, +를 기준으로 split하여 다 더한다.
4. flag가 안 세워졌을 경우, flag를 세우고 3의 값을 더한다.
5. flag가 세워졌을 경우, 3의 값을 뺀다.

• flag는 처음 작성한 로직과 동일한 역할을 한다

이렇게 작성하니 불필요하게 반복되는 로직들이 사라졌고, 단계별 코드의 목적이 명확해졌다. 그래서 코드를 작성하기 훨씬 편했고, 문제를 찾거나 수정하는 것 또한 훨씬 편해졌다.

코드

• 코드