[BaekJoon] 백준 1541번_잃어버린 괄호 for JAVA _그리디 알고리즘

 

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

1541번: 잃어버린 괄호

 

 

 

문제

 

 

---

 

푸는 방법은

 

최소값으로 괄호를 만들기 위해서는 - 뒤의 +가 있는 숫자들까지만 괄호를 쳐주면 된다.

 

 

무슨 말이냐면... 예를 들어

 

 

1+2-3+4+5-10+5 = 2 인데

 

2- 뒤의 3+4+5를 묶고 - 뒤에 10+5를 묶는다는 것이다.

 

그래서 1+2-(3+4+5) -(10+5) = -24 라는 값이 나온다.

 

 

푸는 방법은 바로 떠올렸는데... string으로 받아올 저 케이스를 어떻게 숫자와 +,- 문자로 나눌지 고민했다.

 

다른 사람꺼 참고함 하하하 https://st-lab.tistory.com/148

 

 

 

코드

package Baek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Baek1541 {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] sub = br.readLine().split("-");
		
		int sum = Integer.MAX_VALUE; // 정수 중 가장 큰 값인 2147483647
		
		for(int i = 0; i < sub.length; i++) {
			int temp = 0;
			
			String[] add = sub[i].split("\\+"); // for문 돌 때마다 초기화
			
			for(int j = 0; j < add.length; j++)
				temp += Integer.parseInt(add[j]); // String 배열이라 int화 해줘야함
			
			if(sum == Integer.MAX_VALUE) // 가장 앞에있는 수만 +
				sum = temp;
			else {  // 그 뒤는 다 -
				sum -= temp;
			}		
		}
		
		System.out.println(sum);
				
		
	}

} // 1+2-3+4+5-10+5

 

 

sum을 Integer.MAX_VALUE를 우선 넣어놓고 맨 앞 값인지 확인하는데 사용하였다.

 

왜냐면 맨 앞에는 무조건 숫자가 들어가므로 양수라서 그렇다~

 

ex) sub[] = {{1+2}, {3+4+5}, {10+5}} 이렇게 나오니까 3 - 12 - 15 = -24 의 값이 나오게 된다.

 

 

그리고 +는 메타문자여서 split으로 구분할 때 split("\\+") 이렇게 \\를 넣어줘야한다.~!

 

 

 

 

 

 

성능

 

 

 

 

 

다른 사람들도 이렇게 풀었다. for each문을 주로 사용한듯....!