[BOJ] Q16637 괄호 추가하기

🔗문제 링크

BOJ 16637번

🔒 문제 설명

연산자(+, -, *)와 한자리 수로 주어진 수식을 계산해야 한다.

각 연산자의 우선순위는 없으며 왼쪽부터 차례대로 계산한다.

하지만 수식에 괄호를 추가할 수 있으며, 괄호는 숫자 2개와 연산자 하나로 구성되어야 한다.

또한 중첩된 괄호는 사용할 수 없을 때, 수식의 최대값을 구하시오.

🧾 입력 예시

9
3+8*7-9*2

첫줄에는 수식의 길이, 두번째 줄에는 수식이 주어진다.

🔎 출력 예시

136

🔑 문제 풀이

1. 괄호의 구간을 담을 리스트(parenList)를 생성한다.

2. DFS를 통하여 괄호의 구간들을 설정한다.
   ex) [2] : (8*7)
   ex) [2,6] : (8*7), (9*2) 를 의미한다.

3. 괄호 구간은 계산을 한 값으로 업데이트 한 후 리스트를 생성(makeList())한 후(lastList) 최종 계산(calc())한다.

if(dep<=cnt) {
	int idx = 0;
	StringBuilder sb = new StringBuilder();
	for(int parenIdx : parenList) {
		for(int i=idx ; i<parenIdx ; i++) {
			sb.append(str.charAt(i));
		}
		int temp = calc(makeList(str.substring(parenIdx,parenIdx+3)));
		sb.append(temp);
		idx = parenIdx+3;
	}
	sb.append(str.substring(idx));
	List<String> lastList = makeList(sb.toString());
	int sum = calc(lastList);
//	System.out.println(parenList+" : "+sb+" sum: "+sum);
	ret = Math.max(ret,sum);			
}

5. DFS를 반복하여 모든 괄호구간을 탐색하여 max값을 업데이트 한 후 최종값을 출력한다.

💻 전체 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		Main z = new Main();
		z.solution();
	}
	int ret = 0;
	private void solution() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		ret = Integer.MIN_VALUE;
		String str = br.readLine();
		List<Integer> parenList = new ArrayList<>();
		int cnt = str.length()-str.length()/2;
		dfs(str, cnt, 0, -2, parenList);
		System.out.println(ret);
	}
	private void dfs(String str, int cnt, int dep, int befo, List<Integer>parenList) {
		if(dep<=cnt) {
			int idx = 0;
			StringBuilder sb = new StringBuilder();
			for(int parenIdx : parenList) {
				for(int i=idx ; i<parenIdx ; i++) {
					sb.append(str.charAt(i));
				}
				int temp = calc(makeList(str.substring(parenIdx,parenIdx+3)));
				sb.append(temp);
				idx = parenIdx+3;
			}
			sb.append(str.substring(idx));
			List<String> lastList = makeList(sb.toString());
			int sum = calc(lastList);
//			System.out.println(parenList+" : "+sb+" sum: "+sum);
			ret = Math.max(ret,sum);
			
		}else {
			return;
		}
		for(int i=befo+2 ; i<str.length()-1 ; i+=2) {
			if(!parenList.contains(i) && !parenList.contains(i-2)) {
				parenList.add(i);
				dfs(str, cnt, dep+1, i, parenList);
				parenList.remove(parenList.size()-1);
			}
		}
	}
	private int calc(List<String> list) {
		int sum = Integer.parseInt(list.get(0));
		int num = 0;
		for(int i=1 ; i<list.size() ; i+=2) {
			String temp = list.get(i);
			switch (list.get(i)) {
			case "+" :
				sum += Integer.parseInt(list.get(i+1));
				break;
			case "-" :
				sum -= Integer.parseInt(list.get(i+1));
				break;
			case "*" :
				sum *= Integer.parseInt(list.get(i+1));
				break;
			default:
				break;
			}
		}
		return sum;
	}
	private List<String> makeList(String str){
		List<String> ret = new ArrayList<>();
		StringBuilder sb = new StringBuilder();
		for(int i=0 ; i<str.length() ; i++) {
			char ch = str.charAt(i);
			if(!isOperator(str, i)) {
				// 연산자가 아닌경우
				sb.append(ch);
			}else {
				ret.add(sb.toString());
				ret.add(String.valueOf(ch));
				sb = new StringBuilder();
			}
		}
		if(sb.length()!=0)
			ret.add(sb.toString());
//		System.out.println("mL : "+ret);
		return ret;
	}
	private boolean isOperator(String str,int idx) {
		String comp = "+-*/";
		if(str.substring(idx,idx+1).matches("[0-9]")) {
			// 숫자인 경우
			return false;
		}
		if(idx==0) {
			// str의 시작인 경우
			return false;
		}
		if(!comp.contains(str.substring(idx-1,idx))) {
			// idx 앞이  숫자인 경우
			return true;
		}
		return false;
	}
}

📇 결과