[BOJ] 14888. 연산자 끼워넣기

N의 범위를 확인해본 결과 11이므로 nextPermutation()또는 백트래킹을 이용한 순열을 사용하는 문제이다.

하지만 이문제에서 주의할점은 순열을 구해하는 수,기호 에는 중복이 되는 것이 있으므로 무조건 nextPermutation()을 직접 구현해야 풀 수 있는 문제이다. 연산자들을 모아놓은 op배열을 생성후 모든 number에 대하여 연산을 해주면 쉽게 풀어지는 문제이다. 관건은 nextPermutation()의 직접 구현이다.

package online.base;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_14888_연산자끼워넣기 {
    static int N, totalOp;
    static int[] numbers;
    static int[] op;
    static int max,min;
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        
        numbers=new int[N];
        st=new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++)
            numbers[i]=Integer.parseInt(st.nextToken());
        totalOp=N-1;
        op=new int[totalOp];
        st=new StringTokenizer(br.readLine());
        int index=0;
        for(int i=0;i<4;i++) {
            int count=Integer.parseInt(st.nextToken());
            for(int j=0;j<count;j++)
                op[index++]=i;
        }
        max=Integer.MIN_VALUE;
        min=Integer.MAX_VALUE;
        calc();
        System.out.println(max);
        System.out.println(min);
    }
    
    static void calc() {
        
        do {
            int sum=numbers[0];
            
            for(int i=0;i<N-1;i++) {
                if(op[i]==0) {
                    sum+=numbers[i+1];
                }else if(op[i]==1) {
                    sum-=numbers[i+1];
                }else if(op[i]==2) {
                    sum*=numbers[i+1];
                }else if(op[i]==3) {
                    sum/=numbers[i+1];
                }
            }
            
            if(sum>max)
                max=sum;
            if(sum<min)
                min=sum;
            
        }while(nextPermutation());
        
    }
    
    static boolean nextPermutation() {
        int i=totalOp-1;
        
        //1.등호가 < 되는 곳 찾기
        while(i>0 && op[i-1]>=op[i] )
            i--;
        
        if(i==0)
            return false;
        
        //2.arr[i-1]보다 큰 arr[j] 찾기
        int j=totalOp-1;
        while(op[i-1]>=op[j])
            j--;
        
        //3.arr[i-1], arr[j] 교환
        int temp = op[i-1];
        op[i-1]=op[j];
        op[j]=temp;
        
        int k=totalOp-1;
        //4.i부터 N-1까지 오름차순으로 교환
        while(i<k) {
            temp=op[i];
            op[i]=op[k];
            op[k]=temp;
            i++;k--;
        }
        
        
        
        
        return true;
    }
}