BOJ_14888 연산자 끼워넣기 (Java)

문제링크

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

14888번: 연산자 끼워넣기

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 브루트포스

연산자를 끼워 넣는 문제는 브루트포스로 해결하였다. 연산자의 개수는 숫자 배열의 크기 -1 이므로 최대 10개이다. 10개를 순서를 고려하여 나열하는 방법은 최대 10!이므로 시간초과 없이 해결할 수 있다. 따라서, 만들수 있는 모든 연산자의 경우의수를 만들어준 뒤 계산해 주면 쉽게 해결할 수 있다. 

 

구현코드

package boj_14888;

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i =0 ;i< a.length; i++){
            a[i] = sc.nextInt();
        }
        int plusNum = sc.nextInt();
        int minusNum = sc.nextInt();
        int mulNum = sc.nextInt();
        int divNum = sc.nextInt();

        int[] cal = new int[n-1];
        ArrayList<int[]> cals = new ArrayList<>();
        orderCal(cals,cal,plusNum,minusNum,mulNum,divNum,0);

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        int result = 0;
        for(int i = 0; i < cals.size(); i++){
            int x = a[0];
            int y;
            int[] c = cals.get(i);
            for(int j = 1; j < a.length; j++){
                int oper = c[j-1];
                y = a[j];
                if(oper == 1)
                    result = x+y;
                else if(oper == 2)
                    result = x-y;
                else if(oper == 3)
                    result = x*y;
                else{
                    result = x/y;
                }
                x = result;
            }
            if(max < result){
                max = result;
            }
            if(min > result){
                min =result;
            }
            result = 0;
        }
        System.out.println(max);
        System.out.println(min);
    }

    public static void orderCal(ArrayList<int[]> cals, int[] cal, int plusNum, int minusNum, int mulNum, int divNum, int idx){

        if(idx == cal.length){
            int[] result = new int[cal.length];
            for(int i = 0; i < cal.length; i++){
                result[i] = cal[i];
            }
            cals.add(result);
            return;
        }

        if(plusNum != 0){
            cal[idx] = 1;
            orderCal(cals,cal,plusNum-1,minusNum,mulNum,divNum,idx+1);
        }
        if(minusNum != 0){
            cal[idx] = 2;
            orderCal(cals,cal,plusNum,minusNum-1,mulNum,divNum,idx+1);
        }
        if(mulNum != 0){
            cal[idx] = 3;
            orderCal(cals,cal,plusNum,minusNum,mulNum-1,divNum,idx+1);
        }
        if(divNum != 0){
            cal[idx] = 4;
            orderCal(cals,cal,plusNum,minusNum,mulNum,divNum-1,idx+1);
        }
    }
}

 

시간복잡도

시간복잡도는 배열의 크기인 n-1을 나열하는 값이므로 $O(n!)$이다.

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)