BOJ_14888 : 연산자 끼워넣기

👉 문제링크

14888번: 연산자 끼워넣기

---

---

🔸 문제 분석 🔸

• 고정된 위치의 숫자와, 그 사이에 하나 씩 들어갈 수 있는 4종류의 연산자들의 개수가 주어진다.
  • 계산으로 만들 수 있는 값의 최대값과 최소값을 출력한다.
• 연산자 자리를 바꾸면 값이 달라지기 때문에 순열로 풀이할 수 있다.
• 같은 종류의 연산자는 자리를 바꿔도 중복계산이기 때문에 dfs나 nextpermutation으로 중복을 제거할 수 있다.

🔸 순열 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int n, max, min;
    private static int[] numbers, orders, picks;
    private static boolean[] used;

    private static void perm(int idx) { // 연산자 순서 순열, idx : orders에서 현재 고른 연산자 수
        if (idx == n - 1) { // 연산자 모두 고름
//            System.out.println(Arrays.toString(picks));
            cal_all();
        } else {
            for (int i = 0; i < n - 1; i++) {
                if (!used[i]) { // orders의 i번째 연산자 사용 안했으면 사용
                    used[i] = true;
                    picks[idx] = orders[i]; // 사용 연산자 기록
                    perm(idx + 1);      // 순열 재귀
                    used[i] = false;
                }
            }
        }
    }

    private static void cal_all() {
//        print();
        int num = numbers[0];
        for (int i = 1; i < n; i++) {
            num = calc(num, numbers[i], picks[i - 1]);
        }
        max = Math.max(max, num);
        min = Math.min(min, num);
    }

    private static int calc(int num1, int num2, int order) {
        switch (order) {
            case 0:
                return num1 + num2;
            case 1:
                return num1 - num2;
            case 2:
                return num1 * num2;
            case 3:
                return num1 / num2;
        }
        return 0;
    }

    private static void print() {
        char[] os = {'+', '-', '*', '/'};
        System.out.print(max + " " + min + " " + numbers[0]);
        for (int i = 1; i < n; i++) {
            System.out.print(" " + os[picks[i - 1]] + " " + numbers[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        max = Integer.MIN_VALUE;
        min = Integer.MAX_VALUE;

        numbers = new int[n];
        orders = new int[n - 1];
        picks = new int[n - 1];
        used = new boolean[n - 1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        int idx = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            int count = Integer.parseInt(st.nextToken());
            for (int j = 0; j < count; j++) {
                orders[idx++] = i;
            }
        }

        perm(0);

        System.out.println(max + "\n" + min);
    }
}

🔸 코드 해석 🔸

• perm() 메서드에서 n-1개의 연산자를 인덱스로 구분해서 순열로 만들어 사용한다.
  • n-1개를 다 골랐으면, cal_all() 메서드에서 값을 계산하고 최대값, 최소값을 업데이트한다.

 

🔸 DFS 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main { // dfs 풀이
    static int[] numbers, cards;
    static int N, ansMax, ansMin;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        numbers = new int[N];
        cards = new int[4];      // 연산자는 숫자보다 한 개 적음

        ansMax = Integer.MIN_VALUE;
        ansMin = Integer.MAX_VALUE;

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

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

        dfs(0, numbers[0], cards[0], cards[1], cards[2], cards[3]);

        System.out.println(ansMax);
        System.out.println(ansMin);
    }
    
    private static void dfs(int idx, int tmp, int a, int b, int c, int d) {
        if (idx == N - 1) {
            ansMax = Math.max(tmp, ansMax);
            ansMin = Math.min(tmp, ansMin);

            return;
        }

        if (a > 0) {
            dfs(idx + 1, tmp + numbers[idx + 1], a - 1, b, c, d);
        }
        if (b > 0) {
            dfs(idx + 1, tmp - numbers[idx + 1], a, b - 1, c, d);
        }
        if (c > 0) {
            dfs(idx + 1, tmp * numbers[idx + 1], a, b, c - 1, d);
        }
        if (d > 0) {
            dfs(idx + 1, tmp / numbers[idx + 1], a, b, c, d - 1);
        }
    }
}

🔸 코드 해석 🔸

• dfs() 메서드에서 4가지 연산자(+, -, *, /)의 개수가 남아있으면 하나씩 사용하며 재귀하는 방식으로 중복없이 모든 경우를 비교해본다.
• 계산 값을 매개변수로 들고다니는 경우가, 값을 따로 저장후 더하고 빼는 방식보더 조금 더 빨랐다.

 

🔸 NP🔸

import java.util.Arrays;
import java.util.Scanner;

public class Main { // np 풀이
    static int[] cards;
    static int ansMax, ansMin, N;
    static int[] numbers;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        numbers = new int[N];
        cards = new int[N - 1];      // 연산자는 숫자보다 한 개 적음

        ansMax = Integer.MIN_VALUE;
        ansMin = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            numbers[i] = sc.nextInt();
        }

        int cardIdx = 0;
        for (int i = 0; i < 4; i++) {
            int count = sc.nextInt();
            for (int j = 0; j < count; j++) {
                cards[cardIdx++] = i;
            }
        }
//        System.out.println(Arrays.toString(cards));

        Arrays.sort(cards);

        do {
            //print();
            cal_all();
        } while (np());

        System.out.println(ansMax);
        System.out.println(ansMin);
    }

    private static boolean np() {
        // step1. 뒤쪽부터 꼭대기를 찾는다. (꼭대기 바로 앞이 교환할 자리)
        int n = cards.length;
        int i = n - 1;
        while (i > 0 && cards[i - 1] >= cards[i])
            i--;

        if (i == 0) // 이미 마지막 순열임
            return false;

        // stemp2. 꼭대기 바로 앞(i-1) 자리에 교환할 값을 뒤쪽부터 찾는다.
        int j = n - 1;
        while (cards[i - 1] >= cards[j]) --j; // 무조건 하나를 찾는다(꼭대기가 있기 때문)

        // step3. 꼭대기 바로 앞(i-1)자리와 그 자리값보다 한 단계 큰 자리(j) 수와 교환
        swap(cards, i - 1, j);

        // step4. 꼭대기부터 맨 뒤까지 오름차순으로 정렬
        int k = n - 1;
        while (i < k) {
            swap(cards, i++, k--);
        }
        return true;
    }

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

    private static void cal_all() {
        int num = numbers[0];
        for (int i = 1; i < N; i++) {
            num = calc(num, numbers[i], cards[i - 1]);
        }
        ansMax = Math.max(ansMax, num);
        ansMin = Math.min(ansMin, num);
    }

    private static int calc(int num1, int num2, int order) {
        switch (order) {
            case 0:
                return num1 + num2;
            case 1:
                return num1 - num2;
            case 2:
                return num1 * num2;
            case 3:
                return num1 / num2;
        }
        return 0;
    }

    private static void print() {
        char[] os = {'+', '-', '*', '/'};
        System.out.print(ansMax + " " + ansMin + " " + numbers[0]);
        for (int i = 1; i < N; i++) {
            System.out.print(" " + os[cards[i - 1]] + " " + numbers[i]);
        }
        System.out.println();
    }
}

🔸 코드 해석 🔸

• Next Permutaion 을 활용해서 중복없이 연산자를 고른 방법이다.
  • 입력된 연산자 번호를 1차원 배열 cards에 저장하고 오름차순 정렬한다.
  • np로 연산자 번호를 바꿔가며 나올 수 있는 중복 제거 된 순열로 계산하고 최대 최소값을 업데이트한다.
  • 메서드 호출이 dfs보다 적으므로 더 빠르다.

---

🔸 end 🔸

• 간단한 문제라고 생각했는데, dfs와 np로 풀이를 해볼 수 있어서 좋은 공부가 되었다.
• 순서대로 순열, dfs, np 풀이 결과이다.