[BOJ-16637] 괄호추가하기 -Java

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

16637번: 괄호 추가하기

package 시뮬레이션_review;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class boj_16637_괄호추가하기 {
	static int N;
	static int max;
	static  List<Integer> num;
	static  List<Character> op;
	public static void main(String[] args) throws NumberFormatException, IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		 N=Integer.parseInt(br.readLine());
		 String inputData = br.readLine();
		 
		 max=Integer.MIN_VALUE;
		 num=new ArrayList<>();
		 op=new ArrayList<>();
		 
		 for(int i=0; i<N; i++) {
			 char data = inputData.charAt(i);
			 if(Character.isDigit(data)) num.add(data-'0');
			 else op.add(data);
		 }
		 
		 solve(num.get(0), 0);
		 System.out.println(max);
		
	}
	private static void solve(int result, int opIdx) {
		if(opIdx>=op.size()) {
			max=Math.max(result, max);
			return;
		}
		
		solve(cal(result, num.get(opIdx+1), opIdx), opIdx+1);
		
		if(opIdx+1 < op.size()) {
			int next=cal(num.get(opIdx+1), num.get(opIdx+2), opIdx+1);
			
			solve(cal(result, next, opIdx), opIdx+2);
			
		}
		
		
		
	}
	private static int cal(int result, int num, int opIdx) {
		char getOp=op.get(opIdx);
		switch (getOp) {
		case '+':
			return result+num;
		case '-':
			return result-num;
		case '*':
			return result*num;
		case '/':
			return result/num;
		}
		return 0;
	}

}

 

 

소요시간 : 1시간 10분

 

괄호를 어떻게 쳐야할 지 고민을 많이 했습니다. 

코드 적는 시간은 약 20분내외 였고 나머지 시간은 계속 설계를 했습니다.

 

수식의 길이가 19이기 때문에 연산자수가 많아도 10개이하입니다! 그래서 DFS를 사용했습니다.

 

로직을 살펴보면

 

1+2-3*4  가 입력으로 들어온다면

 

1+2-3*4+5
1+2-3*(4+5)
1+2-(3*4)+5

1+(2-3)*4+5

1+(2-3)*(4+5)

처럼 5가지의 경우가 있습니다.

 

1.이전 계산결과와 오른쪽의 피연산자를 피연산자로하여 현재 연산자의 연산을 수행!

2.이전 계산결과와 오른쪽의 연산자의 연산수행결과를 피연산자로 해서 현재 연산자의 연산을 수행!

 

을 재귀함수로 구현하면 됩니다!

 

뭔가 말로 설명하기가 되게 어렵네요...