Baekjoon[16637] - 괄호 추가하기

링크

16637번: 괄호 추가하기

문제설명

• 완전탐색

문제풀이

• 완전탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main16637_timeout {

    public static int cal(int a, int b, char oper) {

        switch (oper) {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        }
        return -1;
    }


    public static int Ans=Integer.MIN_VALUE;
    public static int Temp;
    public static int N;
    public static int[] input_num;
    public static char[] input_oper;
    public static ArrayList<Integer> lst = new ArrayList<Integer>();
    public static int[] num;
    public static char[] oper;

    public static void Search(int cnt, int brace) {
        if(cnt>=N/2) {
//            lst에 맞추어서 괄호만 연산한 후의 string 생성
//            System.out.println(lst);
            num = new int[N/2-brace];
            oper = new char[N/2-brace-1];

            int num_cnt=0;
            int oper_cnt=0;
            for (int i = 0; i < N/2; i++) {
//                () 경우
                if(lst.contains(i)) {
                    num[num_cnt]=(cal(input_num[i],input_num[i+1],input_oper[i]));
                    num_cnt++;
//                    마지막인 경우는 마지막 숫자 추가 안함
                    if(i!=N/2-1) {
                        oper[oper_cnt]=(input_oper[i+1]);
                        oper_cnt++;
                    }
//                    마지막에서 2번째인 경우 마지막 숫자 추가
                    if(i==N/2-2) {
                        num[num_cnt]=(input_num[i+2]);
                        num_cnt++;
                    }
                    i++;
                }
//                ()아닌 경우
                else {
                    if(i==N/2-1) {
                        num[num_cnt]=(input_num[i]);
                        num_cnt++;
                        oper[oper_cnt]=(input_oper[i]);
                        oper_cnt++;
                        num[num_cnt]=(input_num[i+1]);
                        num_cnt++;
                    }
                    else {
                        num[num_cnt]=(input_num[i]);
                        num_cnt++;
                        oper[oper_cnt]=(input_oper[i]);
                        oper_cnt++;
                    }
                }
            }
//            System.out.println(num);
//            System.out.println(oper);
//            생성 string 기준으로 연산
            Temp=0;
            Temp = cal(num[0], num[1], oper[0]);
            for (int i = 1; i < oper.length; i++) {
                Temp = cal(Temp, num[i+1], oper[i]);
            }
//            최대값 갱신
            Ans = Math.max(Ans, Temp);
            return;
        }

//        cnt 번째 연산자 괄호 씌움
        lst.add(cnt);
//        그 다음 연산자는 무조건 안되므로 cnt+4
        Search(cnt+2,brace+1);
        lst.remove(lst.size()-1);

//        cnt 번째 연산자 괄호 안씌움
        Search(cnt+1,brace);
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/16637.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        char[] input = br.readLine().toCharArray();
        input_num = new int[N/2+1];
        input_oper = new char[N/2];

        for (int i = 0; i < N; i++) {
            if(i%2==0) {
                input_num[i/2]=input[i]-'0';
            }
            else {
                input_oper[i/2]=input[i];
            }
        }
        Search(0,0);

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• 시간초과뜸
  • string 쭉쓰면 음수처리가 힘듦
  • -> 음수 처리를 할 수 있는 array 만들어서 처리함
  • -> 연산을 위한 배열 생성을 2번함
  • -> string에서 음수처리를 하면 배열생성이1번만 하기떄문에 더 빠를수도있음

잘한점

• 문제 이번엔 제대로 읽음 -> 연산자 우선순위 같고, 괄호가 겹칠수 없음 -> 좀더 쉬워짐