백준 14888 연산자 끼워넣기 JAVA(백 트래킹)

 

아주 애먹은 문제였기 때문에,, 따로 포스팅 할 가치가 있는 문제였습니다.

 

제가 짠 코드가 빠른 실행 시간을 보장하지는 않지만, 일반적인 백 트래킹 문제들과 비슷한 코드 구조를 가지고 있기 때문에 좀 더 쉽게 이해 할 수 있는 코드라고 생각하기에 포스팅을 하게 되었습니다.

 

<코드 개념>

입력받은 N-1개의 연산자를 백 트래킹을 이용해 완전탐색한 후, 모든 연산자 수열의 경우의 수에 대하여 각각 합을 구해 최댓값과 최솟값을 찾아냅니다.

 

ex ) 연산자 배열이 (1, 0, 1, 0)일 경우

경우의 수 : "+*", "*+" 

 

해당 String 변수를 ArrayList에 모두 넣어준 후, ArrayList에 들어있는 연산자 수열들을 이용해 수들의 합을 완전탐색 합니다.

 

백 트래킹 방식이긴 하지만, 백 트래킹이 수행되는 요소들간 연결관계가 없기 때문에 dfs 방식이기도 합니다.

 

 

<JAVA 전체 코드>

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

public class Operator_insert {
    public static ArrayList<String> possibles = new ArrayList<>();
    public static void find_possible(int[] operator, int depth, String answer, int operator_sum){
        if (depth == operator_sum){
            possibles.add(answer);
        } else{
            for(int i=0;i < operator.length; i++) {
                if (operator[i] > 0) {
                    operator[i] -= 1;
                    answer += convert(i);
                    find_possible(operator, depth + 1, answer, operator_sum);
                    answer = answer.substring(0, answer.length()-1);
                    operator[i] += 1;
                }
            }
        }
    }
    public static void print_max_min(int[] nums){
        ArrayList<Integer> sums = new ArrayList<>();
        for(int i=0;i< possibles.size();i++){
            int temp = 0;
            int index = 0;
            while(index < possibles.get(i).length()){
                if (index == 0){
                    temp += calculate(nums[index], nums[index+1], possibles.get(i).charAt(index));
                } else{
                    temp = calculate(temp, nums[index+1], possibles.get(i).charAt(index));
                }
                index += 1;
            }
            sums.add(temp);
        }
        System.out.println(Collections.max(sums));
        System.out.println(Collections.min(sums));
    }
    public static int calculate(int operand1, int operand2, char operator){
        if (operator == '+'){
            return operand1 + operand2;
        } else if (operator == '-'){
            return operand1 - operand2;
        } else if (operator == '*'){
            return operand1 * operand2;
        } else{
            return operand1 / operand2;
        }
    }
    public static String convert(int index){
        if (index == 0){
            return "+";
        } else if(index == 1){
            return "-";
        } else if(index == 2){
            return "*";
        } else{
            return "/";
        }
    }
    public static void main(String[] args) throws IOException{
        try{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int N = Integer.parseInt(br.readLine());
            /* 들어오는 숫자들 */
            int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            /* 각 연산자별 개수들 */
            int[] operators = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            find_possible(operators, 0, "", Arrays.stream(operators).sum());
            print_max_min(nums);
        } catch(IOException e){
            e.printStackTrace();
        }
    }
}

 

convert, calculate, print_max_min 메소드는 각각 기본적인 기능을 하고 있기 때문에, 잘 읽어보시면 쉽게 이해하실 수 있을듯 합니다.

 

convert : 입력받은 연산자의 인덱스를 조사하며 char형 연산자 기호로 바꿔주는 메소드 입니다.   

+ : 0,  - : 1,  * : 2,  / : 3

calculate : 피연산자 두개를 받아서, 주어진 연산자로 계산을 진행해주는 메소드 입니다.

 

print_max_min : 완전탐색이 완료된 모든 경우의 수에 대해서 합계를 구한 후, 최댓값과 최솟값을 출력해주는 메소드 입니다.

 

<부분별 설명>

    public static void find_possible(int[] operator, int depth, String answer, int operator_sum){
        if (depth == operator_sum){
            possibles.add(answer);
        } else{
            for(int i=0;i < operator.length; i++) {
                if (operator[i] > 0) {
                    operator[i] -= 1;
                    answer += convert(i);
                    find_possible(operator, depth + 1, answer, operator_sum);
                    answer = answer.substring(0, answer.length()-1);
                    operator[i] += 1;
                }
            }
        }
    }

백 트래킹이 적용되는 find_possible 메소드입니다.

 

operator_sum은 처음에 주어지는 연산자 배열의 각 요소들의 합입니다.

 

줄별 설명

 

2 : 연산자를 하나 선택 할 때 마다 depth(깊이)가 1씩 증가하므로, 깊이가 주어진 연산자의 개수와 같아진다면 모든 선택을 완료한 경우가 됩니다. 따라서 결과값을 ArrayList인 possibles에 넣어줍니다.

 

6 : operator(주어진 연산자 배열)의 값이 0 이상일 경우, 해당 연산자가 아직 선택되지 않는 상태이기 때문에 분기합니다.

 

이후 코드들은, 분기 후 answer에 선택한 연산자를 이어 붙이는 과정입니다.

find_possible 메소드가 실행되어진 후에는, 다시 이전 상태로 돌아가야 하므로 연산자 배열에 사용한 연산자의 값을 다시 1 증가시켜주고, answer에 이어붙여진 해당 연산자를 제거해줍니다.

 

 

 

 

짜고나서 보면 어려운 코드는 아니였지만, "연산자 배열"과 "N개의 수로 이루어진 수열"이라는 두개의 배열을 가지고 백트래킹을 하려하니 조금 어려웠습니다.

 

주어진 N개의 수열은 항상 순서를 처음과 같이 유지해야하기 때문에, "연산자"만 가지고 백 트래킹을 한다고 생각하면 더 쉬울것 같습니다.