[백준/JAVA] 14888번 : 연산자 끼워넣기(BruteFroce, 순열)

 

문제

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

14888번: 연산자 끼워넣기

 

 

 

 

 

풀이

주어진 연산자들의 순열을 순차적으로 탐색하며 최솟값과 최댓값을 찾는다.

연산자들의 다음 순열을 찾아 나가므로, 연산자 배열을 string이 아닌 int 배열로 만든다.

숫자 n개가 주어질 때, 연산자의 총 개수는 n-1개이므로, 연산자 배열의 길이는 n-1이다.

+를 0, -를 1, x를 2, %를 3으로 하여 연산자 배열에 저장한다.

연산자를 배열로 저장하는 코드는 다음과 같다.

//연산자 배열
int[] operators = new int[n-1];

for(int i = 0; i<n; i++)
    nums[i] = sc.nextInt();

int idx = 0;
for(int i = 0; i<4; i++){
    int k = sc.nextInt();
    for(int j = 0; j<k; j++) {
        operators[idx] = i;
        idx++;
    }
}

 

 

이제, 연산자 순열의 다음 순열을 구해보자. 

private static boolean next_perm(int[] operators){
	int i = operators.length-1;

	//내림차순의 시작점을 구한다
    while(i>0 && operators[i-1]>=operators[i]) i--;

	//다음 순열은 존재하지 않으므로 false
    if(i<=0) return false;

    int j = operators.length-1;

	//i-1번째 수보다 큰 수 중 가장 index값이 큰 숫자를 구한다
    while(operators[j]<=operators[i-1])
        j--;

	//i-1번째 수와 j번째 수를 바꾼다
    swap(i-1, j, operators);
    
    j = operators.length-1;

	//i번째부터의 숫자는 모두 오름차순이 되어야 한다
    while(i<j){
        swap(i, j, operators);
        i++;
        j--;
    }
    return true;
}

 

 

연산자의 다음 순열을 구해, 식을 계산하는 코드는 다음과 같다.

private static int cal(int[] nums, int[] operators){
    int result = 0;

    for(int i = 0; i<nums.length-1; i++){
        if(i==0) result = nums[i];
        if(operators[i] == 0)
            result += nums[i+1];
        else if(operators[i] == 1)
            result -= nums[i+1];
        else if(operators[i] == 2)
            result = result *nums[i+1];
        else if(operators[i] == 3)
            result /= nums[i+1];
    }
    return result;
}

 

 

다음 순열이 없을 때까지 연산자 순열을 통해 계산된 결과를 리스트에 저장하고, 최댓값, 최솟값을 출력하면 된다.

 

 

 

 

 

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static boolean next_perm(int[] operators){
        int i = operators.length-1;

        while(i>0 && operators[i-1]>=operators[i]) i--;

        if(i<=0) return false;

        int j = operators.length-1;

        while(operators[j]<=operators[i-1])
            j--;

        swap(i-1, j, operators);
        j = operators.length-1;

        while(i<j){
            swap(i, j, operators);
            i++;
            j--;
        }
        return true;
    }

    private static void swap(int i, int j, int[] arr){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int cal(int[] nums, int[] operators){
        int result = 0;

        for(int i = 0; i<nums.length-1; i++){
            if(i==0) result = nums[i];
            if(operators[i] == 0)
                result += nums[i+1];
            else if(operators[i] == 1)
                result -= nums[i+1];
            else if(operators[i] == 2)
                result = result *nums[i+1];
            else if(operators[i] == 3)
                result /= nums[i+1];
        }
        return result;
    }

    public static void main(String[] args){
        List<Integer> results = new ArrayList<Integer>();
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        //숫자 배열
        int[] nums = new int[n];

        //연산자 배열
        int[] operators = new int[n-1];

        for(int i = 0; i<n; i++)
            nums[i] = sc.nextInt();

        int idx = 0;
        for(int i = 0; i<4; i++){
            int k = sc.nextInt();
            for(int j = 0; j<k; j++) {
                operators[idx] = i;
                idx++;
            }
        }


        do {
            results.add(cal(nums, operators));
        } while (next_perm(operators));

        System.out.println(Collections.max(results));
        System.out.println(Collections.min(results));
    }
}