[백준-1541번 자바/java] 잃어버린 괄호 _디버깅의 눈물

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

1541번: 잃어버린 괄호

 

 

 

 

 

잃어버린 괄호 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

56178

28993

23038

51.230%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

예제 입력 2 복사

10+20+30+40

예제 출력 2 복사

100

예제 입력 3 복사

00009-00009

예제 출력 3 복사

0

 

 

 

 

---

 

 

 

 

 

 

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

 

 

 

-괄호를 통해 해당 식의 값을 최소로 만들기 위해서는, -부분에 괄호를 적용해 그 크기가 최대로 되면 된다.

 

//예시1)
55-50+40

 

-예제 1)을 예시로 볼 때, 해당 식이 최소로 되기 위해서는 55-(50+40)이 되어야 한다.

-즉, 주어진 식을 '-'를 기준으로 나눈 후, +로된 수들을 모두 합한 후 -부호 처리하면 된다.

-주의해야 할 점은 첫번째 자리의 합은 양수여야한다는 점이다.

 

 

// 자체 예시)
55-40+30-70-10+20

// 괄호 적용 정답
55-(40+30)-70-(10+20)

 

-자체 예시를 볼 때,

1)주어진 식을 '-'를 기준으로 나누면, 55, (40+30), 70, (10+20)이고,

2)+로 된 수를 모두 합하면 55, 70, 70, 30이다.

3)첫번째 자리를 제외한 나머지 수를 모두 합한 후 -부호 처리를 하면 -170이고,

4)마지막으로 양수인 첫번째 자리수와 더하면 -115이다.

 

 

 

 

 

2. split("\\+") 이용

 

String[] temp = s[i].split("\\+");

 

-String의 내장함수 split을 통해 -와 +를 잘라주는 부분이 있다.

-이때 +의 경우 split("+")로 작성한다면 에러가 발생한다.

-split의 경우 매개변수로 정규식을 받기 때문이다.

-따라서 +가 정규표현식으로 인식되지 않도록 "\\+"처리를 통해 이스케이프 처리를 해야한다.

 

 

 

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


class Main{
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		// -를 기준으로 split
		String[] s = st.nextToken().split("-");
		
		solution(s);
		
	}// end of main
	
	
	
	static void solution(String[] s) {
		
		int answer = 0;
		
		for(int i=0; i<s.length; i++) {
				// +를 기준으로 split
				String[] temp = s[i].split("\\+");
				
				// +부분의 총합을 담아주는 임시변수
				int tempInt = 0;
				
				for(int j=0; j<temp.length; j++) {
					tempInt += Integer.parseInt(temp[j]);
				}
				
				// i가 첫번째라면,
				if(i==0) {
					// 양수처리 후 합산
					answer += tempInt;
				}
				// i가 첫번째가 아니라면,
				else {
					// 음수처리 후 합산
					answer -= tempInt;
				}
			
		}
		
		
		System.out.println(answer);
		
	}
	
	
	
} // end of Main