[백준] 16637번 : 괄호 추가하기 - 자바[Java]

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

16637번: 괄호 추가하기

풀이

DFS(재귀함수)를 사용하여 풀이하였다.

 

main() 로직

1. 수식에서 숫자와 연산자를 구분하여 각각 ArrayList<Integer> numbers, ArrayList<Character> operators에 저장한다.

2. 재귀함수를 호출하여 DFS를 수행한다.

    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int n = Integer.parseInt(br.readLine());
    	String expression = br.readLine();
    	
    	for (int i = 0; i < n; i++) {
    		char ch = expression.charAt(i);
    		if (Character.isDigit(ch)) {
    			numbers.add(ch-'0');
    		}
    		else operators.add(ch);
    	}
    	
    	dfs(numbers.get(0), 0);
    	
    	System.out.println(max);

 

void dfs(int num, int opIdx): num은 이전에 계산한 값, opIdx는 이번 연산에 사용할 연산자의 인덱스다.

1. opIdx가 operators의 크기와 같거나 크다면 더 이상 연산을 진행하지 못하므로 max값과 비교하여 업데이트한다.

2. 괄호 없이 계산한 다음 dfs() 호출

3. 현재 연산자 다음에 연산자가 있다면, 다음 연산자에 괄호가 있다고 생각하여 값을 미리 계산하고, 그 값을 num과 이번 연산자를 사용하여 계산한 결과값으로 dfs() 호출

    public static void dfs(int num, int opIdx) {
    	if (opIdx >= operators.size()) {
    		max = Math.max(max, num);
    		return;
    	}
    	
    	// 괄호 없이 계산
    	int result = calc(num, numbers.get(opIdx+1), opIdx);
    	dfs(result, opIdx + 1);
    	
    	// 오른쪽에 있는 2개의 값에 괄호 추가하여 계산
    	if (opIdx + 1 < operators.size()) {
    		result = calc(numbers.get(opIdx+1), numbers.get(opIdx+2), opIdx+1);
    		result = calc(num, result, opIdx);
    		dfs(result, opIdx+2);
    	}
    }

 

코드

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

public class Main {
	
	static ArrayList<Integer> numbers = new ArrayList<>();
	static ArrayList<Character> operators = new ArrayList<>();
	static int max = Integer.MIN_VALUE;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	int n = Integer.parseInt(br.readLine());
    	String expression = br.readLine();
    	
    	for (int i = 0; i < n; i++) {
    		char ch = expression.charAt(i);
    		if (Character.isDigit(ch)) {
    			numbers.add(ch-'0');
    		}
    		else operators.add(ch);
    	}
    	
    	dfs(numbers.get(0), 0);
    	
    	System.out.println(max);
    }
    
    public static void dfs(int num, int opIdx) {
    	if (opIdx >= operators.size()) {
    		max = Math.max(max, num);
    		return;
    	}
    	
    	// 괄호 없이 계산
    	int result = calc(num, numbers.get(opIdx+1), opIdx);
    	dfs(result, opIdx + 1);
    	
    	// 오른쪽에 있는 2개의 값에 괄호 추가하여 계산
    	if (opIdx + 1 < operators.size()) {
    		result = calc(numbers.get(opIdx+1), numbers.get(opIdx+2), opIdx+1);
    		result = calc(num, result, opIdx);
    		dfs(result, opIdx+2);
    	}
    }
    
    public static int calc(int num, int nextNum, int opIdx) {
    	char operator = operators.get(opIdx);
    	
    	switch (operator) {
    		case '+': 
    			return num + nextNum;
    		case '-':
    			return num - nextNum;
    		case '*':
    			return num * nextNum;
    	}
    	
    	return 0;
    }
    
}

 

참고

• https://steady-coding.tistory.com/36