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

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

1541번: 잃어버린 괄호

코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str = scan.next();
		int sum = 0;
		int minusSum = 0;
		String[] sArr1 = str.split("-");	// '-' 기준으로 잘라서 배열에 담기

		// 첫 '-'가 오기 전까지는 다 더해야함
		String[] sArr2 = sArr1[0].split("\\+");
		
		for(String s : sArr2) {
			sum += Integer.parseInt(s);
		}
		
		// 첫 '-' 이후의 숫자는 다 더한후 sum에서 빼면 최솟값
		for(int i=1; i<sArr1.length; i++) {
			String[] sArr3 = sArr1[i].split("\\+");
			for(String s : sArr3) {
				minusSum += Integer.parseInt(s);
			}
		}
		
		System.out.println(sum - minusSum);
		scan.close();
	}
}

 

풀이

위 문제를 보며 -가 나올 때까지 수를 더하며 빼주는게 최솟값인걸 파악했지만,,

구현은 못했다. 결국 다른 힌트를 참고해서 풀었다.

첫번째 -가 오기 전까지의 숫자는 모두 더해주어야한다.

예를 들어서 설명해보면 ,,

 

40 + 20 - 30 - 60 + 40 - 20 + 50 이란 문자열이 있을때,

 

(40+20) - 30 - (60+40) - (20+50) 이 된다.

1. 따라서 먼저 입력받은 문자열을 "-" 를 기준으로 자르고,

2. 첫 "-"가 오기 전의 첫 번째 원소는 모두 더한다.

3. 그 후에는 "-"가 오기 전까지의 원소는 모두 더한 후 첫 번째 원소의 합에서 빼면 최솟값이 된다.

 

 

 

코드 2

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str = scan.next();
		int minSum = 0;	// 최솟값
		String[] sArr = str.split("-");	// 입력받은 문자열을 "-"를 기준으로 자르기.
		for(int i=0; i<sArr.length; i++) {
			String[] sArr2 = sArr[i].split("\\+"); // sArr배열의 각 원소를 "+"를 기준으로 자르기.
			int sum = 0;	// sArr 배열의 각 원소에 대한 합
			for(String s : sArr2) {
				sum += Integer.parseInt(s);
			}
			// 가장 첫번째 원소를 제외한 나머지 원소의 합은 - 이다.
			if(i != 0) {
				sum *= -1;
			}
				minSum += sum;
		}
		scan.close();
		System.out.println(minSum);
	}

}

위 코드는 첫 번째 원소를 배열에 따로 설정하지않고, if문을 통해 첫번째원소와, 그 외 원소에 대해 조건을 처리해주었다.