[그리디] 백준 잃어버린 괄호 1541번

[그리디] 백준 잃어버린 괄호 1541번

---

문제 설명

세준이는 양수와 +,-,그리고 괄호로 식을 만들었다.

괄호를 모두 지우고,

다시 괄호를 적절히 쳐서 이 식의 최소값을 구하려고 한다.

이 식의 최소값을 구하라.

 

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고,

가장 처음과 마지막 문자는 숫자이다.

그리고 연속해서 두 개 이상의 연산자가 나타나지 않고,

5자리보다 많이 연속되는 숫자는 없다.

수는 0으로 시작할 수 있다.

입력으로 주어지는 식의 길이는 50보다 작거나 같다.

---

출력

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

 

** 풀이 방법

 

가장 큰 수를 빼야 최소값이 나온다.

 

식을 입력 받는다.

ex) 55-50+40

Scanner sc = new Scanner(System.in);
String sik = sc.nextLine();

 

뺄셈은 가장 마지막에 할 것이기 때문에

"-"기준으로 문자를 잘라서 배열에 담는다.

배열 안에 있는 값들로 덧셈을 해야한다.

arr = { "55", "50+40" }

String[] arr = sik.split("-");

 

덧셈을 할 mySum메서드를 만들어준다.

전달받은 문자를 "+" 기준으로 문자열을 잘라서

각 문자열들을 정수로 형변환해서

sum에 더해준다.

static int mySum(String a) {
    int sum = 0;
    String temp[] = a.split("[+]");
    for (int i=0; i<temp.length; i++) {
        sum += Integer.parseInt(temp[i]);
    }
    return sum;
}

 

가장 첫 숫자를 제외하고

mySum의 반환값을 answer에 빼준다.

for문이 끝나고 answer를 출력한다.

for (int i=0; i<arr.length; i++) {
    int temp = mySum(arr[i]);
    if (i==0) 
        answer += temp;
    else
        answer -= temp;
}
System.out.println(answer);

 

i = 0 →  mySum("55") →  temp = {"55"} →  sum = 55 → answer = 55

i = 1 → mySum("50+40") →  temp = {"50", "40"} → sum = 90 →  asnwer = -35

 

<>전체 코드 </>

import java.util.*;

public class Main {

	public static void main(String[] args) {
		int answer = 0;
		Scanner sc = new Scanner(System.in);
		String sik = sc.nextLine();
		String[] arr = sik.split("-");
		for (int i=0; i<arr.length; i++) {
			int temp = mySum(arr[i]);
			if (i==0) 
				answer += temp;
			else
				answer -= temp;
		}
		System.out.println(answer);
	}
	static int mySum(String a) {
		int sum = 0;
		String temp[] = a.split("[+]");
		for (int i=0; i<temp.length; i++) {
			sum += Integer.parseInt(temp[i]);
		}
		return sum;
	}

}