백준 14888번. 연산자 끼워넣기 (Java, Python)

Problem

• 문제 링크

수열과 연산자가 주어졌을 때 조합하여 만들수 있는 최소값과 최대값을 구하는 문제입니다.

Solution

연산자가 배치될 수 있는 모든 경우의 수를 구한 후에 MAX, MIN 값을 구하는 문제입니다.

단순하게 재귀로 풀수도 있지만 순열을 이용하여 풀었습니다.

모든 경우의 수를 봐야 하고 순서는 중요하지 않기 때문에 간단하게 swap 으로 순열을 구현하였습니다.

1. operator 배열을 만들어서 각 연산자 갯수에 대해 1, 2, 3, 4로 넣기
2. operator 배열에 대해서 순열 돌리기
3. 순열로 인한 경우의 수 마다 연산값을 계산하여 max, min 값 구하기
4. 출력

위와 같은 순서로 진행하였습니다.

파이썬은 좀더 예전에 풀었던 거라 연산자를 아예 +, -, *, / 로 배열에 저장했는데 순열을 구한 뒤 계산한다는 전체적인 로직은 같습니다.

Java Code

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

class Main {
    static int n;
    static int[] a;
    static int[] operator;
    static int max = -987654321;
    static int min = 987654321;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

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

        n = stoi(br.readLine());
        a = new int[n];
        operator = new int[n - 1];

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

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for (int i = 0; i < 4; i++) {
            int temp = stoi(st.nextToken());

            // 1:덧셈, 2:뺄셈, 3:곱셈, 4:나눗셈
            for (int j = 0; j < temp; j++) {
                if (i == 0) operator[idx++] = 1;
                else if (i == 1) operator[idx++] = 2;
                else if (i == 2) operator[idx++] = 3;
                else operator[idx++] = 4;
            }
        }

        // 계산 시작
        permutation(0);
        System.out.println(max);
        System.out.println(min);
    }

    // 순열 구하기
    static void permutation(int depth) {
        if (depth == n - 1) {
            calculate();
            return;
        }

        for (int i = depth; i < n - 1; i++) {
            swap(depth, i);
            permutation(depth + 1);
            swap(depth, i);
        }
    }

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

    // 각 순열에 대해서 연산 후 max, min 값 찾기
    static void calculate() {
        int result = a[0];

        for (int i = 0; i < n - 1; i++) {
            if (operator[i] == 1) result += a[i + 1];
            else if (operator[i] == 2) result -= a[i + 1];
            else if (operator[i] == 3) result *= a[i + 1];
            else result /= a[i + 1];
        }

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

Python Code

# -*- coding: utf-8 -*-
 
import sys
import itertools
 
def setOperatorList(N, add, sub, mul, div):
    operator = []
 
    for i in range(N-1):
        if add > 0:
            operator.append("+")
            add -= 1
        elif sub > 0:
            operator.append("-")
            sub -= 1
        elif mul > 0:
            operator.append("*")
            mul -= 1
        elif div > 0:
            operator.append("/")
            div -= 1
 
    return operator
 
 
def solve(N, A, operator):
    result = A[0]
 
    for i in range(N-1):
        if operator[i] == "+":
            result = result + A[i+1]
        elif operator[i] == "-":
            result = result - A[i+1]
        elif operator[i] == "*":
            result = result * A[i+1]
        elif operator[i] == "/":
            result = int(result / A[i+1])
 
    return result
 
if __name__ == '__main__':
    N = int(sys.stdin.readline())
    A = [i for i in list(map(int, sys.stdin.readline().split()))]
    add, sub, mul, div = map(int, sys.stdin.readline().split())
    
    operatorList = setOperatorList(N, add, sub, mul, div)
 
    operators = itertools.permutations(operatorList)
 
    maxVal = -sys.maxsize
    minVal = sys.maxsize
 
    for operator in operators:
        result = solve(N, A, operator)
 
        if result < minVal:
            minVal = result
        
        if result > maxVal:
            maxVal = result
 
    print(maxVal)
    print(minVal)