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

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

1541번: 잃어버린 괄호

📚 문제

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

📝 문제 해결

최솟값을 만들기 위해서는 최대한 큰 수를 빼주어야 한다. 즉, 덧셈 먼저 계산한 뒤 빼주면된다.

10-20+30-40+50 => 10-(20+30)-(40+50)

         1) 뺄셈을 기준으로 문자열을 분리시킨다.
         2) 덧셈을 기준으로 문자열을 분리시킨 후 더해준다.
         3) 더해준 값들을 빼준다.

💻 코드

import java.util.*;
 
public class BOJ1541 {    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        String [] arr = input.split("\\-");
        
        int result = add(arr[0]);
        for(int i=1; i<arr.length; i++) {
            result -= add(arr[i]);
        }
        System.out.println(result);
        
    }
    
    public static int add(String i) {
        String []arr = i.split("\\+");
        int result = 0;
        for(String k : arr) {
            result += Integer.parseInt(k);
        }
        
        return result;
    }
    
}

split 함수의 구조를 다시 살펴보니 해당 함수는 정규표현식을 통해 문자를 인식한다고 한다.
정규표현식에 따르면 +가 의미하는 바는 "앞 문자가 1개 이상 존재할 수 있다." 라는 뜻이라고 한다.
정규표현식에서 특수문자인 +를 표현하기 위해서는 "\\+"로 표기해야한다.

[출처 : https://everydayidid.tistory.com/13]

 

💡 다른 사람 코드

StringTokenizer를 이용해 문자열을 분리시켜줄 수 있다.

int sum = Integer.MAX_VALUE;	// 초기 상태 여부 확인을 위한 값으로 설정 
StringTokenizer subtraction = new StringTokenizer(br.readLine(), "-");
 
while (subtraction.hasMoreTokens()) {
	int temp = 0;
 
	// 뺄셈으로 나뉜 토큰을 덧셈으로 분리하여 해당 토큰들을 더한다.
	StringTokenizer addition = new StringTokenizer(subtraction.nextToken(), "+");
			
	// 덧셈으로 나뉜 토큰들을 모두 더한다. 
	while (addition.hasMoreTokens()) {
		temp += Integer.parseInt(addition.nextToken());
	}
			
	// 첫 번째토큰인 경우 temp값이 첫 번째 수가 됨
	if (sum == Integer.MAX_VALUE) {
		sum = temp;
	} else {
		sum -= temp;
	}
}

[출처 : https://st-lab.tistory.com/148]