링크

16637 괄호 추가하기

문제

풀이

어떻게 풀어야겠다라는 생각은 다 했는데 괄호를 쳐서 계산하는 부분에서 시간을 엄청 썼다.
풀이는 되게 간단하다.

먼저 백트래킹을 통해 괄호의 모든 경우의 수를 계산했다.
1번 예시로 들자면 괄호를 치는 방법이

이런 경우의 수가 있다. 그리고 괄호의 갯수를 체크해서 분기조건으로 넣어줬다.
괄호의 갯수는 숫자 / 2 거나 (연산자갯수 + 1) / 2로 둘 중 편한거 하나 쓰면 된다.
그리고 숫자와 연산자를 따로 정리해서 넣어줬다.

나는 숫자길이만큼 배열을 만들어서 true인 경우 그 인덱스와 다음 인덱스가 괄호를 친다고 생각하고 문제를 풀었다.

이까진 순조롭게 풀었지만 괄호를 묶어서 우선 계산하는 것에 되게 힘들었다.
이런 저런 시도 끝에 내게 가장 편한 방법은 괄호 친 녀석들만 먼저 계산하고 다시 그것을 배열에다가 넣고 계산했다. 즉 무슨말이냐면

인덱스 0번째랑 1번째 괄호가 묶여 있으니
(3+8)을 먼저 계산하고 새로운 배열에다가 숫자와 연산자를 넣어서 한번에 계산했다.

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;
import java.util.List;

public class Main{
    public static List<Integer> numberList = new ArrayList<>();
    public static List<String> operatorList = new ArrayList<>();
    public static boolean[] visited;
    public static int answer = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        String[] arr = br.readLine().split("");

        for(int i=0;i<arr.length;i++){
            if(i % 2 == 0){
                numberList.add(Integer.parseInt(arr[i]));
            } else{
                operatorList.add(arr[i]);
            }
        }

//        System.out.println(numberList);
//        System.out.println(operatorList);
        visited = new boolean[numberList.size()];

        dfs(0, 0, numberList.size() / 2);
        System.out.println(answer);

    }

    public static void dfs(int dept, int lastIdx, int limit){
        if(dept == limit){
//            System.out.println(Arrays.toString(visited));
            cal();
            return;
        }

        for(int i=lastIdx;i<visited.length;i++){
            if(!visited[i] && i+1 < visited.length){
                visited[i] = true;
//                visited[i+1] = true;
//                System.out.println(Arrays.toString(visited));
                cal();
                dfs(dept+1, i+2, limit);
                visited[i] = false;
//                visited[i+1] = false;


            }
        }


    }

    //visited에 true이면 괄호
    //아니면
    public static void cal(){
        List<Integer> afterNum = new ArrayList<>();
        List<String> afterOper = new ArrayList<>();

        for(int i=0;i<visited.length-1;i++){
            if(!visited[i]) afterOper.add(operatorList.get(i));
        }

        int idx = 0;
        while(true){
            if(visited[idx]){
                int sum = 0;
                int prev = numberList.get(idx);
                int next = numberList.get(idx+1);

                if(operatorList.get(idx).equals("+")){
                    sum += prev + next;
                } else if(operatorList.get(idx).equals("-")){
                    sum += prev - next;
                } else{
                    sum += prev * next;
                }

                afterNum.add(sum);
                idx+=2;

            } else{
                afterNum.add(numberList.get(idx));
                idx++;
            }

            if(idx == visited.length) break;
        }

//        System.out.println(afterNum);
//        System.out.println(afterOper);


        int result = afterNum.get(0);
        for(int i=0;i<afterOper.size();i++){
            if(afterOper.get(i).equals("+")){
                result += afterNum.get(i+1);
            } else if(afterOper.get(i).equals("-")){
                result -= afterNum.get(i+1);
            } else{
                result *= afterNum.get(i+1);
            }
        }

//        System.out.println(result);
//        System.out.println("----------------");

        answer = Math.max(result, answer);

    }


}