[백준] 잃어버린 괄호 (java) Greedy
2020-03-02
잃어버린 괄호 (백준> Greedy)
문제설명
세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.
출력
첫째 줄에 정답을 출력한다.
예제 입력 1 복사
55-50+40
예제 출력 1 복사
-35
풀이
package Greedy;
import java.util.*;
//50min
public class beak_잃어버린괄호 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
//처음은 무조건 +부터 시작하니까 -나오기 전까지 더해주고 이 값에서 나중에 나온 값을 빼준다
String s_split[] = s.split("-"); //- 다 뺴준다 --> +와 숫자가 섞여있다
String tmp[] = s_split[0].split("\\+"); // 첫 - 전 숫자들은 +로만 이루어져있으니까 따로 전부 더한다! -->숫자만 들어있다
int first = 0;
for(int i=0;i<tmp.length;i++)
first = first + Integer.parseInt(tmp[i]);
int sum=0;
for(int i=1;i<s_split.length;i++) {
tmp = s_split[i].split("\\+");
for(int j=0; j<tmp.length; j++)
sum = sum + Integer.parseInt(tmp[j]);
}
System.out.println(first-sum);
}
}
후기 (50min)
좀 익숙해졌다 싶으면 바로 어려워지는 greedy.. dp… 으아ㅏㅏ
문제가 뭔지도 이해를 못하겠는게 많아지니 원.. 더 열심히 하자 복습도
참고 링크