[JAVA / 자바] 백준 1541번 - 잃어버린 괄호 (실버 2)

 문제 

세준이는 양수와 +, -, 그러고 괄호를 가지고 식을 만들었다. 그러고 나서 세준이는 괄호를 모두 지웠다.

그러고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

---

 입력 

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

---

 출력 

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

---

---

 문제 접근 방법 

괄호가 없는 식이 입력으로 주어진다. 이때 우리는 식의 결괏값을 최소로 만들어야 한다.

식에 입력되는 연산자는 +와 -뿐이다. 그렇다면 식의 결괏값이 최소가 되기 위해서는 빼주는 값을 최대한으로 만들어야 한다. 빼는 값을 만들려면 - 연산자가 필요한데 입력된 식에서 -가 처음 발견되면 그 뒤에 나오는 수는 연산자가 무엇이 나오던 모두 더해 -가 나오기 전의 합에서 나온 후의 합을 빼주면 입력된 식의 최소 결괏값이 구해진다.

 

아직 왜 그렇게 되는지 이해가 되지 않는다면 다음 예시를 들어 도와주겠다.

1 + 3 + 4 - 3 + 2 - 3 + 3

위와 같은 식이 입력으로 주어졌다. 이 식의 결괏값을 최소로 만드는 괄호의 위치는 다음과 같다.

1 + 3 + 4 - (3 + 2) - (3 + 3)

위 식은 다음과 같이 표현해 줄 수 있다.

1 + 3 + 4 - (3 + 2  + 3 + 3)

이 예시를 보면 알 수 있듯이 최초로 -연산자가 식에서 발견되면 - 연산자 앞에 나온 숫자의 합과 뒤에 나온 숫자의 합의 차가 최소가 되는 결괏값이 되는 것이다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

식에 입력되는 연산자는 서로 계산 우선순위가 동일한 연산자이다. 따라서 순서대로 계산이 가능하므로 괄호를 식에 넣어 새로 식을 만들 필요 없이 저장해뒀던 내용을 순차적으로 계산해주면 해결된다. 처음에 괄호를 넣어 식을 다시 만든 후 다시 계산하고 DFS로 괄호를 다 넣어볼 생각까지 했지만, 도저히 아닌 것 같아서 조금 고민해보다가 위 풀이와 같은 방법이 떠오르게 되었다. 요즘 문제를 풀 때 내가 풀고서도 이게 운 좋게 떠올라서 해결이 된 건지 아님 내가 실력으로 푼 건지 헷갈릴 때가 종종 있다. 생각보다 내가 수학 알고리즘 문제에 약한 것 같다. 이번 자료구조 공부가 끝나면 수학 공부를 시작해보아야겠다.

 

---

 문제 원본 

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

1541번: 잃어버린 괄호

 알고리즘 분류 

• 수학
• 문자열
• 그리디 알고리즘
• 파싱