BOJ 1541 잃어버린 괄호

1541번: 잃어버린 괄호

그리디 문제이다.

일단 식에서 최소값이 되게하려면 마이너스 부호가 나온 곳부터 다음 마이너스 부호가 나올 곳까지 괄호를 쳐주면 된다. 

이를 이용해서 문제를 풀어보면,

1. 일단 식의 첫번째 문자는 무조건 숫자이므로, 숫자를 읽어서 sum에다 저장해준다
2. 두번째 문자부터 읽는데, 해당 문자가 마이너스이면, 괄호를 쳐서 괄호 안에 해당하는 모든 숫자의 합을 현재 sum에다가 빼준다.
3. 만약 해당 문자가 플러스이면, 역시나 마이너스부호가 나올때까지 모두 더해서 sum에다 더해준다.
4. 문자열을 숫자로 파싱해주는 메서드를 따로 만들었다. 리턴값은 pair 클래스로, 파싱된 숫자가 끝난 인덱스와, 파싱된 숫자를 반환한다.
5. operation 메서드는 괄호치는 메서드이다. 즉, 마이너스부호가 나올 때까지 모든 값을 숫자로 파싱하고, 더해준다. 리턴값은 더해진 숫자의 합과, 연산이 끝난 자리의 인덱스-1 이다. 

내가 한 실수는

1. 플러스가 먼저나오는 경우를 생각 안했다.
2. 숫자 문자열 처리를 처음에 그냥 인덱스 하나로 받아버렸다 (--) 매우 초보적인 실수..
3. 마이너스부터~ 마이너스 나오기 전까지 괄호 칠 때, 괄호 시작 인덱스 인자 넘겨주는데에서 마이너스 인자부터 넘겨줘버렸다. 이러면 괄호를 아예 못치게된다! 따라서 해당 인덱스 +1 을 넘겨줘야한다. 또한, 앞으로 시작할 인덱스를 다시 넘겨받을 때에는 인덱스-1을 해줘야한다. 그래야만 '-'부호가 포함된다 

import java.util.*;
import java.io.*;

class pair{
	int sum;
	int idx;
	pair(int sum, int idx){
		this.sum=sum;
		this.idx=idx;
	}
}

//logic
//-을만나면 -만난 이후~ 다시 -을만날때까지의 숫자들을에 괄호를 친다.
public class Main {
	public static void main(String[]args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[]s;
		s=br.readLine().split("");
		pair p= parseToInt(0,s);//첫숫자를 숫자로 바꾸어서 저장한다. 
		int sum = p.sum;
		int idx=p.idx;
		
		
		for(int i = idx ; i < s.length;i++) { //첫번째 연산자부터시작 
			if(s[i].equals("-")) { //연산자가  - 라면, 괄호치기 
				pair p2 = operation(i+1,s);
				i = p2.idx;  // 인덱스변경 
				sum-=p2.sum; // 다 더해준 연산자를 -에서 빼준다.
			}
			else if(s[i].equals("+")) { //플러스 연산자 
				pair p3 = operation(i+1,s); //다 더해준다. 
				i=p3.idx;
				sum+=p3.sum;
				
			}
		}
		System.out.println(sum);
	}
	
	private static pair parseToInt(int idx, String[]s) { //문자열 -> 숫자로 파싱 
		String number="";
		while(idx<s.length && !s[idx].equals("+") && !s[idx].equals("-")) {
			number+=s[idx];
			idx++;
		}
		pair p = new pair(Integer.parseInt(number),idx);
		return p;
	}
	
	
	private static pair operation(int idx, String[]s) {
		int sum = 0;
		while(idx<s.length&&!s[idx].equals("-")) {
			if(!s[idx].equals("+") && !s[idx].equals("-")) { //숫자일 때 
				pair tmp = parseToInt(idx,s);
				sum+=tmp.sum;
				idx=tmp.idx;
			}
			else idx++; //숫자가 아닐 때 
		}
		pair p = new pair(sum,idx-1);
		return p;
	}
	
}