솔직히 풀이하는데 오래 걸렸다. (2~3시간)

[백준]16637번 괄호추가하기

16637번: 괄호 추가하기

• 수식의 길이가 N
  • 0~9까지 정수, +, -, x 의 연산자로 이루어짐.
  • 정수로 시작 —→ (연산자 → 정수) 가 반복된다. =⇒ N은 홀 수 일 수 밖에.
  • 연산자 우선순위가 모두 같다. → 수식 계산은 왼쪽에서부터 순서대로 한다.
• "괄호"를 추가하면, 우선순위가 생기게 된다.
  • 괄호는 - 💥괄호 안에 연산자가 하나만 💥들어가도록 해야 한다.
  • 괄호를 💥 중첩하여 사용할 수 없다. 💥
• 수식이 주어졌을 때, 💥[ 괄호를 적절히 추가해 ]💥 만들 수 있는 식의 결과의 💥최댓값💥을 구하라.
  • 추가하는 괄호 개수 제한 없다.
  • 결과는 2^31보다 작고, -2^31 보다 크다 .
• N은 1이상 19 이하
  • 삼성역량문제라 그런가.. 왠지 또 완전탐색의 삘이 느껴진다.

풀이생각

• 괄호의 중복을 허용하지 않는 것이 다행인 문제라고 느껴진다.

• 숫자와 마주치면

  • 괄호를 넣거나

  • 넣지 않는다.

    • 특히, 이미 괄호 안에 들어간 숫자인 경우 넣으면 안된다

      3+8*9
      여기서 3을 보고, 괄호를 해야겠다 생각을 함. 
      그런데 8을 마주함 ! -> 하지만 8은 이미 괄호에 들어간 상태 
      (3+8)

  • 🧭🧭 N이 19이하 → 1+2*9 → 숫자 10개, 연산자 9개 → 최대 2^10가지정도이기 때문에 완전탐색이 가능할 듯 하다. 🧭🧭

• 숫자를 마주칠 때 마다, 1. 현숫자에 대해 괄호를 넣을 것 2. 현숫자에 대해 괄호를 넣지 않을 것 —> 이 두가지 경우 모두를 해 보아야 한다.

  • 재귀함수를 사용할 것이고, 재귀함수에서는, int idxes[3]을 사용한다.

    
    idxes[0,+연산자의 index,0]을 넣어둔다. 0은 이제까지의 연산결과이고, idxes[1]은 연산자이다
    매 번 idexes는 idxes[0]과 idxes[1] 이 채워져 있도록 한다. 

  • 여기서 '1. 현 숫자에 대해 괄호를 넣을 것 ' —> 의 경우에는, express(idx) express(idx+1) express(idx+2) 의 연산이 일어나는 것이다. ( 이 문제는, 괄호의 중첩이 없기에 , 바로 이 연산 결과를 return해 오도록 한다 )

    • 이를 위해서는 현 idx가 마지막 숫자가 아니어야 한다는 조건이 있다.
    • 연산 결과로 얻을 것을 바로, 현재 인자로 넘어와있는 idxes[0]에 대해 idxes[1]의 연산자로 연산을 진행 —> 새로운 int[] next 배열의 0번째 원소로 저장한다.

  • 여기서 2. 현 숫자에 대해 괄호를 넣지 않을 것

    • 따라서 idexes와의 연산만을 하여 next[0]에 저장한다.

  • 숫자가 아닌 경우, → 연산자인 경우, → 연산자의 index를 idxes[1]에 저장한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;

public class Main{

   public static int n;
    public static StringBuilder sb = new StringBuilder("+");
    public static String express; // express길이는 원래식길이+1
    // 원래식이 길이가 3이면 -> 4가 되고, 마지막 idx는 3이되니까..
    public static int max =Integer.MIN_VALUE;
    public static void Setting() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        sb.append(br.readLine());
        express = sb.toString();

        //"_3+8*7-9*2"
        // 0123456789 -> 홀수인 idx에만 숫자가 위치한다.
    }

    // idxes[0] 에는 항상 값이 있으면 좋겠다.. idxes[1]에는 '+'를 해서 첫 번째 호출 때 줬으면 좋겠다.
    // idxes[0] 에는 항상 이제까지의 값이 존재한다.
    // 3개 단위로만 연산을 하면 된다.
    public static void solve(int idx,int[] idxes){

        if(idx>n){
            // max인지 체크한다.
            if(max<idxes[0]) max = idxes[0];
            return;
        }
        int[] next = new int[2];
        int temp =0;
        // 정수인지 확인 : +,-,* 이 ascii코드상 더 작은 수를 갖는다.
        // 정수인 경우 1. 이미 괄호가 쳐져 있는 경우
        if(express.charAt(idx)-'0'>=0){
            // 1. 괄호를 쳐서 넘길 것인가 -> 먼저 괄호 연산 값을 얻어오고, 다음 호출하는 것은.. 현재 idx +3
            // 괄호를 쳐서 넘기려면 현재 idx가 정수임에도, n보다작은 idx여야 함.
            if(idx<n){
                // 현재 idx부터 괄호를 쳤을 때 연산되는 값 -> temp
                temp = cal(express.charAt(idx)-'0',express.charAt(idx+2)-'0',idx+1);
                // idxes로 넘어온 값들 과 temp를 연산시키기
                next[0]=cal(idxes[0],temp,idxes[1]);
                solve(idx+3,next);
            }
            // 2. 괄호를 치지 않고 넘길 것인가 --> 괄호를 치지 않고 넘길 것인가에서도 경우
            next[0]=cal(idxes[0],express.charAt(idx)-'0',idxes[1]);
            solve(idx+1,next);
        }
        else{
            next[0]=idxes[0];
            // 무조건 이 연산자를 추가 해 주도록 해야 함.
            next[1]=idx;
            solve(idx+1,next);
        }
    }
    // opidx는 연산자의 idx
    public static int cal(int n1,int n2,int opidx){
        char op = sb.charAt(opidx);
        switch (op){
            case '+':
                return n1+n2;
            case '-':
                return n1-n2;
            case '*':
                return n1*n2;
        }
        return 0;
    }
    public static void main(String[] args) throws IOException {
        Setting();
        if(n==1){
            max = express.charAt(1)-'0';
            System.out.println(max);

            return;
        }
        solve(1,new int[]{0,0,0});
        System.out.println(max);

    }
}

풀이에 어려움을 느꼈었다.

1. 3개 단위로 계산.
2. 완전탐색을 사용.
3. 재귀함수를 사용해야함
   인 것 같은데, 숫자를 마주쳤을 때, 여기서 괄호를 생성할지 말지 두 가지 경우를 모두 해 보는 것을 어떻게 구현해야할지를 모르겠었다.

• 결국은 int[] idxes라는 자료구조를 인자로 전달하는 식으로 구현함..

다른 사람 풀이를 보았다. → DFS 문제라고 한다.

아하 그렇다. 결국 내가 - 완전탐색 + 재귀함수 + 어떤 값을 넘겨줘야 한다 —> 라고 생각했던 것도

매 번 두 가지 outgoing path가 존재하였기 때문이다. DFS 문제가 맞다.

그리고 내가 계속해서 고민했던 것은, "이제까지의 연산값" 만을 pass해 줄 것인가, (n1 op n2)에서 (n1, op) 를 계속 해서 넘겨 줘야 하는 가 였다.

나는 결국 (n1,op)를 계속해서 넘겨주는 것을 택하였다. → 이 과정에서 solve함수를 호출 할 때 마다 int[3]의 배열을 생성하는 과정을 거쳐야 했다.