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

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

6

1 2 3 4 5 6

2 1 1 1

 

 Output 

54

-24

수와 수 사이에 연산자를 임의로 넣어서 식의 결과가 최대 최소인 것을 구하시오.

※ 연산자의 순서는 바꿀 수 있지만 주어진 수의 순서를 바꿀수 없습니다.

    ex) 1-2÷3+4+5*6 = 54 

    ex) 1*2+3÷4-5×6 = -24

* 사칙연산 우선순위를 무시하고 앞에서부터 진행합니다.

    따라서, 0으로 나누는 경우는 없습니다. ex) 5 ÷ 0 (x)

* 나눗셈의 경우 몫만 취합니다. (분모가 음수인 경우는 없습니다.)

    {(음수)÷(양수)}의 경우 음수를 양수로 바꿔 계산한 후 그 몫을 음수로 바꿉니다.

 

구현 사항

- 연산자를 완전탐색하여 가능한 경우의 수를 구합니다. ← 중복 없는 순열

- 모든 경우의 수 중 최댓값과 최솟값을 구합니다. 

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;


public class Main {
    
    static List<String> operatorList;
    static List<Integer> operand;
    static int min =Integer.MAX_VALUE, max=Integer.MIN_VALUE;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new  InputStreamReader(System.in));
           BufferedWriter bw = new BufferedWriter(new  OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        
        // 피연산자를 저장해둔다.
        StringTokenizer st = new StringTokenizer(br.readLine());
        operand = new ArrayList<>();
        for(int i=0; i<N; i++) {
            operand.add(Integer.parseInt(st.nextToken()));
        }
        
        int[] operator = new int[4];
        operatorList = new ArrayList<>();
        
        // 입력받은 연산자개수 만큼 해당 연산자를 우선 리스트에 보관한다.
        String[] opr = {"+", "-", "*", "/"};
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++) {
            operator[i] = Integer.parseInt(st.nextToken());
            while(operator[i]-- > 0) {
                // 개수만큼 해당 되는 연산자 기호를 넣는다.
                operatorList.add(opr[i]);
            }
        }
        // 순열을 위한 방문 표시
        boolean[] visited = new boolean[operatorList.size()];
        List<String> list = new ArrayList<>();
        
        // 연산자를 순열로 재구성하고 계산결과를 구한다.
        permutation(list, visited);
        
        // 정답 출력
        bw.write(max + "\n");
        bw.write(min + "\n");
        bw.flush(); bw.close();
    }

    private static void permutation(List<String> list, boolean[] visited) {
        if(list.size() == operatorList.size()) {
            
            int result = calculate(list);
            min = min > result ? result : min;
            max = max < result ? result : max;
            return;
        }
        
        for(int i=0; i<operatorList.size(); i++) {
            // 아직 사용하지 원소라면
            if(!visited[i]) {
                // 방문 표시
                visited[i] = true; list.add(operatorList.get(i));
                permutation(list, visited);                
                visited[i] = false; list.remove(list.size()-1);
            }
        }
        
    }

    private static int calculate(List<String> list) {
        // 제일 처음 피연산자로 초기화 해둔다.
        int result = operand.get(0);
        // 연산자와 피연산자의 개수가 맞지 않은 경우는 없으므로 차례대로 연산의 겨로가를 구한다.
        for(int i=1; i<operand.size(); i++) {
            int target = operand.get(i);
            String operator = list.get(i-1);
            if(operator.equals("+")) result += target;
            else if(operator.equals("-")) result -= target;
            else if(operator.equals("*")) result *= target;
            else if(operator.equals("/")) {
                if(result < 0) { // 분자가 음수인 경우
                    result = Math.abs(result) / target;
                    result *= -1;
                }else {
                    result = result / target;
                }
            }
        }
        return result;
    }
}