BOJ14888_연산자끼워넣기

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

문제정리

1. N개의 수로 이루어진 수열

2. N-1개의 연산자가 주어지며 연산자는 + - * /

3. 주어진 수의 순서를 바구면 안된다

4. 식의 계산은 무조건 앞에서부터 진행

5. 나눗셈은 정수 나눗셈으로 몫만 취한다

6. 음수를 양수로 나눌 때는 C++14의 기준을 따른다

즉, 양수로 바꾼뒤(음수를) 몫을 취하고 그 몫을 음수로 바꾼다

7. N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과

최소인 것을 구하는 프로그램을 작성

8. +의 개수 , -의 개수 , *의 개수 , /의 개수

문제issue

1. / 할 때 조건 생각

2. 같은 연산자 있을 때 순열의 개수를 줄일 수 있는 방법?

해결흐름

1. 숫자는 그냥 배열에 넣고 쓴다

2. 연산자도 전체 개수 크기만큼의 배열 생성해서 각각의 개수 만큼 배열에 넣는다

3. 연산자 배열로 순열을 돌린다

4. 순열 한개 마다 바로바로 계산

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
 
    private static int[] number_arr;
    private static boolean[] oper_visited;
    private static char[] oper_arr;
    private static int N;
    private static char[] perm_arr;
    private static int max_result;
    private static int min_result;
    private static int[] arr_clone;
 
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine().trim());
        number_arr = new int[N];
        arr_clone = new int[N];
        oper_visited = new boolean[N - 1];
        oper_arr = new char[N - 1];
        perm_arr = new char[N - 1];
        max_result = Integer.MIN_VALUE;
        min_result = Integer.MAX_VALUE;
        int[] oper_check = new int[4];
        List<Character> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        for (int i = 0; i < N; i++) {
            number_arr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine().trim(), " ");
        for (int i = 0; i < 4; i++) {
            oper_check[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < 4; i++) {
            if (i == 0) {
                for (int j = 0; j < oper_check[i]; j++) {
                    list.add('+');
                }
            } else if (i == 1) {
                for (int j = 0; j < oper_check[i]; j++) {
                    list.add('-');
                }
            } else if (i == 2) {
                for (int j = 0; j < oper_check[i]; j++) {
                    list.add('*');
                }
            } else if (i == 3) {
                for (int j = 0; j < oper_check[i]; j++) {
                    list.add('/');
                }
            }
        }
        for (int i = 0; i < list.size(); i++) {
            oper_arr[i] = list.get(i);
        }
        // start
        nPm(0);
        System.out.println(max_result);
        System.out.println(min_result);
 
    } // end of main
 
    private static void nPm(int len) {
        if (len == N - 1) {
            // perm_arr을 이용 최솟값 , 최댓값 갱신
            for (int i = 0; i < N; i++) {
                arr_clone[i] = number_arr[i];
            }
//            System.out.println("=================");
            solve();
            return;
        }
        for (int i = 0; i < N - 1; i++) {
            if (!oper_visited[i]) {
                oper_visited[i] = true;
                perm_arr[i] = oper_arr[len];
                nPm(len + 1);
                oper_visited[i] = false;
            }
        }
    }
 
    private static void solve() {
        int number_idx = 0;
        int oper_idx = 0;
        while (true) {
//            System.out.println(Arrays.toString(arr_clone));
            if (number_idx == N - 1)
                break;
            char oper = perm_arr[oper_idx++];
            if (oper == '+') {
                int a = arr_clone[number_idx];
                int b = arr_clone[++number_idx];
                arr_clone[number_idx] = a + b;
            } else if (oper == '-') {
                int a = arr_clone[number_idx];
                int b = arr_clone[++number_idx];
                arr_clone[number_idx] = a - b;
            } else if (oper == '*') {
                int a = arr_clone[number_idx];
                int b = arr_clone[++number_idx];
                arr_clone[number_idx] = a * b;
            } else if (oper == '/') {
                int a = arr_clone[number_idx];
                int b = arr_clone[++number_idx];
                if (b != 0) {
                    if (a < 0) {
                        a = a * -1;
                        int number = a / b;
                        number = number * -1;
                        arr_clone[number_idx] = number;
                    } else if (a >= 0) {
                        arr_clone[number_idx] = a / b;
                    }
                } else if (b == 0) {
                    arr_clone[number_idx] = a;
                }
            }
        }
        if (max_result < arr_clone[number_idx])
            max_result = arr_clone[number_idx];
        if (min_result > arr_clone[number_idx])
            min_result = arr_clone[number_idx];
    }
} // end of class