[알고리즘]_그리디 알고리즘_잃어버린 괄호(백준 No.1541)

문제

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

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

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

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

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

💡 해결과정

• 문제를 본 후 내 방식대로 고민하고 풀어보았지만 계속 오류가 났다,,,
• 이 문제에서 가장 핵심은 플러스 연산부터 하고 마이너스 연산하기 였다.
  예를 들어, 30+40-50+100-20+100에서 가장 최솟값을 구할 수 있는 연산은 (30+40)-(50+100)-(20+100)이라는 소리다.

import java.util.Scanner;

public class No_1541 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);

		String ceremony=sc.nextLine();
		String[] subCeremony=ceremony.split("\\-");
		int answer=0;
		for(int i=0;i<subCeremony.length;i++){

			String[] plusCeremony=subCeremony[i].split("\\+");

			int calc =0;
			for(String item:plusCeremony){
				calc+=Integer.parseInt(item);
			}
			if(i==0){
				answer+=calc;
			} else{
				answer-=calc;
			}
		}

		System.out.println(answer);

	}
}

• 코드 해석
  1, 스캐너로 연산식 받기
  2, split함수로 -앞부분의 식 배열에 저장
  3, for문으로 2번 배열에서 또 +앞부분 숫자 꺼내와서 int형으로 변환 후 더하기
  4, 만약 첫번째 연산이라면-> 정답에 더해주고 (30+40)-(50+100)-(20+100)
  그렇지 않다면 정답에서 연산된 값을 뺀다.(30+40)-(50+100)-(20+100)

🤧 마무리

어렵다아 ㅜ ㅜ 이것도 며칠 뒤에 다시 풀어봐야겠다