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

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q16637.java

괄호를 추가하여 식의 최대값을 얻어내라.
괄호 안에는 1개의 연산자만 있을 수 있으며 괄호는 1중으로만 칠 수 있다. 즉, 2중 괄호 이상은 안된다.
연산자의 기호에 상관없이 앞에서부터 연산을 한다.

처음 생각

어디서 풍문으로 듣기로는 11월 삼성 SW 역량테스트 A형 문제와 비슷하다고합니다.

다음 생각

평범한 식이 주어지면 괄호를 쳐서 최대값이 되도록 만들어야한다. 즉, 식을 계산해 주어야한다.

▶ 따라서 숫자와 식을 분리해서 각각의 List에 넣어주었다.

▶ 식은 숫자가 먼저 시작되므로 부호의 i 번째 index는 식의 i+1 번째 index와 연관이 된다.

다다음 생각

많은 방법이 있겠지만 우선, 어떻게 괄호를 쳤을 때 식이 최대값이 되는지 모르므로 모든 경우를 살펴보았다.

▶ n이 19로 작으므로 비트마스크를 통한 조합을 만들어주었다.

다다다음 생각

Queue나 Stack을 이용해서 숫자와 부호들을 집어넣어주면서 만들어진 조합을 토대로 부호의 해당 index의 상태 배열의 값이 1이라면 이전 숫자를 뽑아 해당 계산을 해준 뒤, 다시 넣어주고 상태 배열값이 0이라면 계산없이 바로 넣어주었다.

▶ 우선 계산의 경우 괄호가 중복되면 안되므로 만약 (x + ( y - z) 와 같은 경우라면 조합을 통해 만들어진 상태 배열값이 연속으로 1 1 로 나타날 것이다. 따라서 앞서 우선 연산을 해주었다면 다음번 상태배열 즉, i 번째라면 i+1 번째의 상태 배열값을 0으로 만들어 주었다. 이를통해 중복 괄호를 없앴다.

▶ 연산자에 상관없이 앞에서부터 계산을 한다 정보가 주어졌으므로 Queue를 이용해서 담아주었다.

다다다다음 생각

상태 배열값이 1인 경우를 모두 계산하였다면, 이제 Queue에 들어가 있던 내용들을 빼내주면서 순서대로 계산을 해주었다.

방안

1) Java 풀이

package baekjoon.q10000;
 
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Q16637 {
    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String t = sc.next();
 
        int[] arrN = new int[n/2+1];
        int[] buho = new int[n/2];
        int idx1 = 0;
        int idx2 = 0;
        // 숫자와 부호 나눠서 받기
        for(int i=0;i<t.length();i++){
            if(i%2==0) arrN[idx1++] = t.charAt(i)-'0';
            else buho[idx2++] = t.charAt(i);
        }
        // 앞에서 부터 연산이니 Queue를 이용해보자
        makePowerSet(n/2,arrN,buho);
        System.out.println(result);
    }
 
    static int result = Integer.MIN_VALUE;
    private static void solve(boolean[] preCul,int[] arrN,int[] arrBuho){
        Queue<Integer> queue = new LinkedList<>();
        // 첫 숫자 담기
        queue.add(arrN[0]);
        // 우선 연산해주기
        for(int i=0;i<preCul.length;i++){
            // 우선 연산이라면 앞의 숫자를 빼서 연산해주기
            if(preCul[i]){
                int tN = ((LinkedList<Integer>) queue).pollLast();
                switch (arrBuho[i]){
                    case '+':
                        queue.add(tN+arrN[i+1]);
                        break;
                    case '-':
                        queue.add(tN-arrN[i+1]);
                        break;
                    case '*':
                        queue.add(tN*arrN[i+1]);
                        break;
                }
                if(i<preCul.length-1) preCul[i+1] = false;
            }else {
                queue.add(arrBuho[i]);
                queue.add(arrN[i+1]);
            }
        }
        // 남은 연산해주기
        int tResult = queue.poll();
        while(!queue.isEmpty()){
            int buho = queue.poll();
            int tN = queue.poll();
            switch (buho){
                case '+':
                    tResult += tN;
                    break;
                case '-':
                    tResult -= tN;
                    break;
                case '*':
                    tResult *= tN;
                    break;
            }
        }
        result = Math.max(result,tResult);
    }
    private static void makePowerSet(long n,int[] arrN,int[] arrBuho){
        boolean[] preCul = new boolean[(int)n];
 
        for(long i=0;i<(1<<n);i++){
            // 조합 만들기
            for(long j=0;j<n;j++){
                if(((1<<j)&i)>0){
                    preCul[(int)j] = true;
                }
            }
            // 만든 조합으로 연산하기
            solve(preCul,arrN,arrBuho);
            for(int j=0;j<n;j++)
                preCul[j] = false;
        }
    }
}