[BOJ] 16637 괄호 추가하기 - JAVA

1. 문제

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

16637번: 괄호 추가하기

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

---

2. 풀이

클래스

• 나중에 보니까 다른 사람들은 클래스 안 만들고 배열 두개로 숫자 따로 연산자 따로 하던데 나는 그 방법이 더 복잡해서 클래스를 만들었다. 덱을 사용하는 데에는 객체 하나가 더 편하다. 평소에 이름을 어떻게 지을 지 고민을 많이 하는데 이번 클래스는 대체 뭘 써야할 지 몰라서 아무거나 담는다는 의미로 X 를 붙여줬다. ㅎㅎ 
• 연산자와 숫자를 둘 다 담기 위해 isNum 변수를 추가했다. 나중에 쓸까봐 만든거지만 결국 안썼다. 그래서 추가 안하고 생성자에만 파라미터로 받아서 구분해도 됐을 것 같다.
• isNum이 true라면 숫자, false라면 연산자이므로 숫자일때는 num에 그대로 담고 연산자일때는 int를 char로 바꿔서 op에 담았다.

private static class X {
   int num;
   boolean isNum;
   char op;

   X(int x, boolean isNum) {
      this.isNum = isNum;
      if(isNum) num = x;
      else op = (char)(x);
   }
}

 

메인

• 문제에서 정답이 int범위를 전부 포함하기때문에 MAX 초기값은 Integer.MIN_VALUE여야 한다. 근데 이 문제가 아니라도 그냥 MAX값은 항상 가능한 가장 작은 값(MIN_VALUE)쓰는게 마음편하다. MIN값도 MAX_VALUE로.
• 입력받은 식은 char 배열로 만들었다. 어차피 숫자는 모두 한 자리 수니까 가능하다.
• findMax가 연산자 뽑으면서 계산시키는 함수인데, 초기값으로 1을 넣은 이유는 가장 첫번째 연산자 위치가 1이기 때문이다. new boolean[]은 방문여부 체크하려고 넣었다.

static int MAX = Integer.MIN_VALUE;
static int N;
static char[] expression;

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   expression = in.readLine().toCharArray();

   findMax(1, new boolean[N]);
   System.out.println(MAX);
}

 

연산자 뽑는 함수

• 결론적으로 조합 함수를 응용해서 만들었는데, 잠깐 착각해서 이 부분을 엄청나게 많이 틀렸다.
• 이 함수의 포인트는 이전 연산자가 뽑혔다면 바로 다음 연산자를 뽑을 수 없다는 것이다.
• 그리고 연산자는 2칸 간격으로 있으므로 다음 재귀호출을 할 때 idx+2를 해야한다.
• 인덱스가 N(총 길이)를 넘어가면 계산하고 끝낸다.
• 나를 방문하지 않고 넘어가는 경우부터 부른다. 그리고 재귀호출이 끝나고 다시 돌아온 뒤에 idx-2번째를 방문한 적이 있다면 나를 방문할 수 없는 경우이므로 끝낸다.
  • 여기서 idx가 1인데 idx-2를 방문하려고 하면 인덱스범위예외가 뜬다. 따라서 idx가 1이 아닐때만 접근할 수 있도록 &&연산자를 사용한다. idx!=1 && visited[idx-2]로 하면 1인 경우 바로 비교를 끝내고 다음 줄로 넘어가므로 예외가 발생하지 않는다.
• 위의 경우가 아니라면 나를 방문한 경우도 불러준다.

private static void findMax(int idx, boolean[] visited) {
      if (idx >= N) {
         calc(visited);
         return;
      }

      visited[idx] = false;
      findMax(idx + 2, visited);
      if (idx != 1 && visited[idx - 2]) return;
      visited[idx] = true;
      findMax(idx + 2, visited);
   }

 

뽑은 연산자로 계산하는 함수

• 이제 내가 왜 클래스를 하나 더 만들었는지 나온다. Deque에 한 번에 넣으려고 그랬다.
• 이 함수는 두 부분으로 나눌 수 있는데, 괄호부분을 계산하고 중간 식 생성하는 부분/중간 식을 가지고 최종 계산을 하는 부분이다.

중간 식 생성하는 부분

• 덱을 이용해서 숫자와 연산자 구분 없이 일단 뒤에 추가한다.
• 넣을 연산자(i번째)가 이미 뽑힌 연산자라면 expression[i+1]에 있는 숫자와 덱의 마지막 숫자를 뽑아서 연산한다.
• 연산한 뒤에 다시 덱의 뒤에 추가한다.

Deque<X> deque = new ArrayDeque<>();
for(int i=0;i<N;i++){
   if(!visited[i]){
      if(i%2==0) deque.addLast(new X(expression[i]-'0', true));
      else deque.addLast(new X(expression[i],false));
   }else{
      char op = expression[i];
      int a = deque.pollLast().num;
      int b = expression[++i]-'0';
      if(op=='+') deque.addLast(new X(a+b,true));
      else if(op=='-') deque.addLast(new X(a-b,true));
      else deque.addLast(new X(a*b,true));
   }
}

 

중간 식으로 최종계산하는 부분

• 결과는 result에 담는다. result의 첫번째 값은 덱의 첫번째 값으로 한다. 
• 덱이 빌 때까지 다음을 반복한다.
  • 연산자, 숫자를 같이 앞에서 뽑는다. 첫번째 값을 이미 뽑았으므로 마지막 숫자까지 항상 이 쌍이 가능하다.
  • result와 지금 뽑은 숫자를 계산한 뒤 그 값을 result에 담는다.
• 최종계산이 끝났다면 static MAX 변수와 result를 비교해 다시 담는다.

int result = deque.pollFirst().num;
while(!deque.isEmpty()){
   char op = deque.pollFirst().op;
   int tmp = deque.pollFirst().num;

   if(op=='+') result += tmp;
   else if(op=='-') result -= tmp;
   else result *= tmp;
}

MAX = Math.max(MAX, result);

 

최종 calc함수

• 보기 헷갈릴까봐 한꺼번에 합친 함수를 다시 올린다. 내용은 같다.

private static void calc(boolean[] visited) {
   Deque<X> deque = new ArrayDeque<>();
   for(int i=0;i<N;i++){
      if(!visited[i]){
         if(i%2==0) deque.addLast(new X(expression[i]-'0', true));
         else deque.addLast(new X(expression[i],false));
      }else{
         char op = expression[i];
         int a = deque.pollLast().num;
         int b = expression[++i]-'0';
         if(op=='+') deque.addLast(new X(a+b,true));
         else if(op=='-') deque.addLast(new X(a-b,true));
         else deque.addLast(new X(a*b,true));
      }
   }

   int result = deque.pollFirst().num;
   while(!deque.isEmpty()){
      char op = deque.pollFirst().op;
      int tmp = deque.pollFirst().num;

      if(op=='+') result += tmp;
      else if(op=='-') result -= tmp;
      else result *= tmp;
   }

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

 

전체 코드

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

public class BOJ_16637_괄호추가하기 {
   static int MAX = Integer.MIN_VALUE;
   static int N;
   static char[] expression;

   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      expression = in.readLine().toCharArray();

      findMax(1, new boolean[N]);
      System.out.println(MAX);
   }

   private static void findMax(int idx, boolean[] visited) {
      if (idx >= N) {
         calc(visited);
         return;
      }

      visited[idx] = false;
      findMax(idx + 2, visited);
      if (idx != 1 && visited[idx - 2]) return;
      visited[idx] = true;
      findMax(idx + 2, visited);

   }

   private static void calc(boolean[] visited) {
      Deque<X> deque = new ArrayDeque<>();
      for(int i=0;i<N;i++){
         if(!visited[i]){
            if(i%2==0) deque.addLast(new X(expression[i]-'0', true));
            else deque.addLast(new X(expression[i],false));
         }else{
            char op = expression[i];
            int a = deque.pollLast().num;
            int b = expression[++i]-'0';
            if(op=='+') deque.addLast(new X(a+b,true));
            else if(op=='-') deque.addLast(new X(a-b,true));
            else deque.addLast(new X(a*b,true));
         }
      }

      int result = deque.pollFirst().num;
      while(!deque.isEmpty()){
         char op = deque.pollFirst().op;
         int tmp = deque.pollFirst().num;

         if(op=='+') result += tmp;
         else if(op=='-') result -= tmp;
         else result *= tmp;
      }

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

   private static class X {
      int num;
      boolean isNum;
      char op;

      X(int x, boolean isNum) {
         this.isNum = isNum;
         if(isNum) num = x;
         else op = (char)(x);

      }
   }
}

---

3. 결과

이 문제를 풀면서 조합 방식은 확실하게 익히게 되었다.