[BOJ] 14888 연산자 끼워넣기 - JAVA

1. 문제

14888번: 연산자 끼워넣기

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.

연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

---

2. 풀이

전역 변수

int N	숫자 개수
int MIN,MAX	최솟값, 최댓값 저장할 변수
int[] picked	뽑힌 연산자 저장
int[] num	숫자 저장
int[] operator	연산자 개수 저장

 

Main

1.  위의 전역변수들에 값을 저장한다.

2.  picked 배열을 만든다.

3.  pick메서드를 호출한다.

4.  MIN, MAX값을 출력한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   StringTokenizer st = new StringTokenizer(in.readLine());
   num = new int[N];
   for (int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
   operator = new int[4];
   st = new StringTokenizer(in.readLine());
   for (int i = 0; i < 4; i++) operator[i] = Integer.parseInt(st.nextToken());

   picked = new int[N - 1];
   pick(0);

   System.out.println(MAX + "\n" + MIN);
}

 

Pick

연산자를 뽑는 메서드다.

1.  0부터 3까지 탐색하면서(덧셈, 뺄셈, 곱셈, 나눗셈) 뽑을 수 있는 연산자(개수가 남은 것)를 picked[cnt]자리에 저장하고 개수에서 하나 뺀다.

2.  pick 재귀호출한다.

3.  재귀에서 돌아온 뒤 연산자의 개수를 되돌려놓는다.

4.  cnt==N-1이라면 연산자를 전부 뽑은 것이다. calc메서드를 호출해서 계산결과를 알아내고, MAX, MIN과 비교해서 적당한 값을 저장한다.

public static void pick(int cnt) {
   if (cnt == N - 1) {
      int result = calc();
      if(MAX<result) MAX = result;
      if(MIN>result) MIN = result;
      return;
   }

   for (int i = 0; i < 4; i++) {
      if (operator[i] == 0) continue;
      picked[cnt] = i;
      operator[i]--;
      pick(cnt+1);
      operator[i]++;
   }
}

 

Calculator

뽑은 연산자를 이용해서 계산한다.

public static int calc() {
   int result = num[0];
   for (int i = 1; i < N; i++) {
      if (picked[i - 1] == 0) result += num[i];
      else if (picked[i - 1] == 1) result -= num[i];
      else if (picked[i - 1] == 2) result *= num[i];
      else result /= num[i];
   }
   return result;
}

 

전체 코드

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

public class BOJ_14888_연산자끼워넣기 {
   static int MIN = 1000000001;
   static int MAX = -1000000001;
   static int[] picked, num, operator;
   static int N;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      StringTokenizer st = new StringTokenizer(in.readLine());
      num = new int[N];
      for (int i = 0; i < N; i++) num[i] = Integer.parseInt(st.nextToken());
      operator = new int[4];
      st = new StringTokenizer(in.readLine());
      for (int i = 0; i < 4; i++) operator[i] = Integer.parseInt(st.nextToken());

      picked = new int[N - 1];
      pick(0);

      System.out.println(MAX + "\n" + MIN);
   }

   public static void pick(int cnt) {
      if (cnt == N - 1) {
         int result = calc();
         if(MAX<result) MAX = result;
         if(MIN>result) MIN = result;
         return;
      }

      for (int i = 0; i < 4; i++) {
         if (operator[i] == 0) continue;
         picked[cnt] = i;
         operator[i]--;
         pick(cnt+1);
         operator[i]++;
      }
   }

   public static int calc() {
      int result = num[0];
      for (int i = 1; i < N; i++) {
         if (picked[i - 1] == 0) result += num[i];
         else if (picked[i - 1] == 1) result -= num[i];
         else if (picked[i - 1] == 2) result *= num[i];
         else result /= num[i];
      }
      return result;
   }
}

---

3. 결과

이전에는 calc메서드에서 if문을 쓰지 않고 switch-case로 풀었다. if문을 사용하면 배열에 3번 접근하고 switch-case는 1번하니 배열 접근 시간도 총 실행시간이 늘어난 데에 영향이 있을 것 같다.