[백준 14888, Java] 연산자 끼워넣기

문제

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

접근방법

 1. 연산자 조합 만들기 (makeOperatorCombination)

 2. 만들어진 연산자 조합 각각에 대해서 수열과연산 (operate)

  

 

소스코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line  = br.readLine();
        StringTokenizer st =new StringTokenizer(line);
        int N = Integer.parseInt(st.nextToken());

        int[] array = new int[N];
        line = br.readLine();
        st = new StringTokenizer(line," ");
        for(int i= 0;i<N; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        int[] operatorNum = new int[4];
        line = br.readLine();
        st = new StringTokenizer(line," ");
        for(int i= 0;i<4; i++){
            operatorNum[i] = Integer.parseInt(st.nextToken());
        }


        ArrayList<Integer> operators = new ArrayList<>();
        for(int index = 0 ;index<operatorNum.length ;index++){
            int count = operatorNum[index];
            while(count>0){
                operators.add(index);
                count --;
            }
        }

        YenSanJa yenSanJa = new YenSanJa(N, array, operators);
        yenSanJa.makeOpertorCombination(0);

        

        bw.write(String.valueOf(yenSanJa.getMax()));
        bw.write("\n");
        bw.write(String.valueOf(yenSanJa.getMin()));
        bw.flush();
        bw.close();

    }
}
class YenSanJa{
    public static final int SUM = 0;
    public static final int SUBTRACTION =1;
    public static final int MULTIPLY=2;
    public static final int DIVISION =3;

    private int N;
    private int[] numArray;
    private ArrayList<Integer> operators;
    private boolean[] isSelectedOperator;
    private  int[] operatorCombination;
    Stack<Integer> numStack;
    ArrayList<Integer> results;

    int max;
    int min;


    YenSanJa(int N, int[] numArray, ArrayList<Integer> operators){
        this.N = N ;
        this.numArray = numArray;
        this.operators = operators;
        isSelectedOperator = new boolean[N-1];
        operatorCombination= new int[N-1];
        max = -1000000000;
        min = 1000000000;

        results = new ArrayList<>();

    }


    public void makeOpertorCombination(int index) {
        if(index>=operatorCombination.length){
            operate(operatorCombination);
        }
        else{
            for(int i=0;i<operators.size();i++){
                if(!isSelectedOperator[i]){
                    isSelectedOperator[i] = true;
                    operatorCombination[index] = operators.get(i);

                    makeOpertorCombination(index+1);
                    isSelectedOperator[i] =false;
                }
            }
        }
    }
    public void operate(int[] operatorCombination) {
        int result= 0;

        numStack = new Stack<>();
        for(int index = numArray.length-1; index>=0; index--){
            numStack.push(numArray[index]);
        }

        for(int index =0;index<operatorCombination.length;index++){
            if(operatorCombination[index]==SUM){
                int num1 =numStack.pop();
                int num2 = numStack.pop();
                numStack.push(num1+num2);
            }
            else if(operatorCombination[index]==SUBTRACTION){
                int num1 =numStack.pop();
                int num2 = numStack.pop();
                numStack.push(num1-num2);

            }
            else if(operatorCombination[index]==MULTIPLY){
                int num1 =numStack.pop();
                int num2 = numStack.pop();
                numStack.push(num1*num2);
            }
            else if(operatorCombination[index]==DIVISION){
                int num1 =numStack.pop();
                int num2 = numStack.pop();
                numStack.push(num1/num2);
            }
        }
        result = numStack.pop();
        results.add(result);

        max = Math.max(max, result);
        min = Math.min(min, result);
    }

    public int getMin(){
        return min;
    }

    public int getMax(){
        return max;
    }

}

 

 

 

 

 

Review

1. 문제를 잘못읽었다. 연산자 조합 * 수열 조합으로 해석하고는 연산자 조합 하나에 대해 수열 조합의 연산 결과를 구했다.

2. 문제를 잘 읽자

3. 언제 초기화 할지! 를 잘 정해야 한다. Stack의 생성을 생성자에서 하면 EmptyStack에러가 난다. 

4. 역시나 N과 M 복습