[백준_1541번] 잃어버린 괄호

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

1541번: 잃어버린 괄호

[문제]

 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

/*
 * 덧셈과 뺄셈으로 이루어진 문자열에서 최솟값을 만들기 위해서는 
 * 덧셈으로 이루어진 부분을 먼저 계산한 후 빼주는 것이다.
 * 뺼셈을 기준으로 분리하면 덧셈으로 이루어진 계산식 들이 나온다.
 * 이 덧셈식들을 먼저 계산한 후 첫 번째 피연산자에서 모두 뺴주면 된다.
 * 이때 첫 번째 피연산자를 식별하지 않고 뺄셈을 진행하면 첫 번째 피연산자가 음수가 되므로
 * 식별해주는 과정이 필요하다.
 */
public class BaekJoon_1541 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int sum=Integer.MAX_VALUE; // 첫 번째 숫자인지 확인하기 위한 값으로 설정
		
		// 입력받은 문자열을 뺄셈으로 분리하여 저장
		String[] arr=sc.next().split("-");
		
		// arr 배열에는 뺄셈으로 분리된 덧셈식의 문자열의 덩어리들이 저장되어 있다.
		for(int i=0;i<arr.length;i++) {
			int temp=0;
			
			// arr2 배열에는 덧셈식의 문자열을 덧셈을 기준으로 분리한 뒤 저장 -> 숫자만 저장되어 있음
			String[] arr2=arr[i].split("\\+");
			
			// String 형식을 Integer로 변경하여 누적합 저장
			for(int j=0;j<arr2.length;j++)
				temp+=Integer.parseInt(arr2[j]);
			
			// 첫 번째 피연산자인 경우 temp 값에 대입
			if(sum==Integer.MAX_VALUE)
				sum=temp;
			// 아니라면 뻴셈 진행
			else 
				sum-=temp;
		}
		System.out.println(sum);
	}
}

 

[고찰]

이번 문제의 정답률을 높았지만 나에게는 쉽지 않았던 문제였다..

 덧셈을 먼저 계산한 후 뺄셈을 계산한다는 알고리즘도 생각해내기까지 시간이 걸렸지만 구현 부분이 더 어려웠다. split() 함수를 사용해 본 경험이 별로 없어서 그런것 같다. 또한 첫 번째 피연산자는 무조건 양수이므로 이 부분까지 뺄셈으로 계산해버리면 오답이 나오기 때문에 해당 피연산자가 첫 번째 토큰인지 아닌지 구별하는 과정 또한 고려해줘야 하기 때문에 생각보다는 까다롭게 느껴졌던것 같다.