[백준알고리즘-JAVA]1541번 풀이(잃어버린 괄호) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 1541번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

 잃어버린 괄호 알고리즘은 문제를 보고 괄호를 일일이 넣어보면서 찾는다면, 복잡한 알고리즘이 짜일 수 있습니다. 반대로 어떠한 방식으로 더하기 빼기를 해야 최소의 값이 나오는지 그 규칙을 알아낸다면 보다 간단한 문제가 될 수 있는 문제입니다.

---

백준 1541 (잃어버린 괄호)

문제

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

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

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

입력

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

출력

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

입력 예제

55-50+40

출력 예제

-35

성공 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static long ans = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(),"-");
		
		while(st.hasMoreTokens()) {
			
			int temp = 0;
			
			StringTokenizer str = new StringTokenizer(st.nextToken(),"+");
			
			while(str.hasMoreTokens()) {
				temp += Integer.parseInt(str.nextToken());
			}
			
			if(ans == Integer.MAX_VALUE) 
				ans = temp;
			else
				ans -= temp;

		}

		System.out.println(ans);
		
		}
	
}

 앞서 말한것처럼 최고의 핵심은 어떻게 해야 + - 의 최솟값을 찾을까?입니다. STEP을 따라가면서 이해해 보도록 하죠

---

알고리즘 흐름도

 입력받기 -> -로 나누기 -> +로 나누기 -> 나눈 값들 더하기 -> 예외 처리해주기 -> 출력하기

---

STEP1 + - 의 최솟값은 어떻게 구할까?

 가장 핵심의 요소인 + -의 최솟값을 어떻게 구할까요?

 

입력 예제에서는 55 - 50 + 40 을 50 - (50 + 40)으로 괄호를 쳐서 최솟값을 차아냈지요. 사실 더 많은 테스트 케이스가 있었다면, 쉽게 예상하실 수 있었겠지만, 하나의 테스트 케이스로는 충분히 답을 내리기가 어려웠었죠. 

 

결국에는 규칙을 찾아보면 바로 - +대로 나누어 계산해 주는 방법입니다.

50 + 70 + 7 - 40 + 90 - 10 - 60 + 80의 최솟값은 어떻게 될까?

 

50 + 70 + 7 - (40+90) - 10 - (60 + 80)이 되어야 하죠.

 

- + 대로 나눈다는 의미는 바로 차례대로 나눈다는 의미입니다. 다음 STEP을 넘어가며 완벽한 이해를 해보도록 하죠

---

STEP2 - + 로 나누어 계산해주기

 

우선 먼저 말한 대로 -로 나누어주어야 합니다.

StringTokenizer st = new StringTokenizer(br.readLine(),"-");
		
		while(st.hasMoreTokens()) {
			

		}

이런 식으로 저는 StringTokenizer를 활용하여 나누어 주었습니다.

그럼 이제 각각 나누어진 st의 토콘들은 +를 포함하고 있는 문자열 일 것입니다. 따러서 우리는 또 한 번 +로 나누어 주 ㄴ다음 모든 수를 temp라는 변수에 담아줄 것입니다.

 

StringTokenizer st = new StringTokenizer(br.readLine(),"-");
		
		while(st.hasMoreTokens()) {
			
			int temp = 0;
			
			StringTokenizer str = new StringTokenizer(st.nextToken(),"+");
			
			while(str.hasMoreTokens()) {
				temp += Integer.parseInt(str.nextToken());
			}
			
			}

여기서의 마지막 핵심은 예외처리사항이 있다는 것입니다.

 

첫 수의 경우는 무조건 +를 해주어야 합니다.

(문제이 있어서 가장 앞과 뒤는 숫자라고 하였으니 -가 올 수가 없기 때문이죠)

 

그 후에 st가 다음 값을 가질 때에는 그때부터는 저희가 "-"로 나누어주었으니 모든 답에 -를 해줍니다.

 

	StringTokenizer st = new StringTokenizer(br.readLine(),"-");
		
		while(st.hasMoreTokens()) {
			
			int temp = 0;
			
			StringTokenizer str = new StringTokenizer(st.nextToken(),"+");
			
			while(str.hasMoreTokens()) {
				temp += Integer.parseInt(str.nextToken());
			}
			
			if(ans == Integer.MAX_VALUE) 
				ans = temp;
			else
				ans -= temp;

		}

 이런 식으로 코드를 구현한다면 답은 ans를 출력만 해주면 끝~