[백준] code.plus(브루트 포스 Part 2,JAVA)16638번, 괄호 추가하기 2

문제 링크

16638번: 괄호 추가하기 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 더하기, 빼기보다 곱하기가 우선순위가 높습니다.

2. 중첩되는 괄호는 사용하실 수 없습니다.

3. 괄호를 추가하는 횟수의 제한은 없습니다.

4. 괄호를 사용하지 않아도 상관없습니다.

5. 주어지는 식에 최대값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 괄호를 놓는 모든 경우를 탐색하여 식의 값을 구합니다.

 

3. 모든 경우 탐색 후 식의 최대값을 결과로 출력합니다.

 

연산 우선순위.

 

괄호() : 1등

괄호가 있는 식은 항상 먼저 계산을 진행합니다.

 

곱하기 :  2등

곱하기는 더하기와 빼기보다 먼저 계산을 진행하며 피연산자에 괄호가 있을 때 괄호를 먼저 진행한 뒤 곱하기를 진행합니다.

 

더하기 , 빼기 : 3등

괄호와 곱하기를 진행한 뒤에 모든 더하기와 빼기를 진행합니다.

 

예를 들어

3 + 2 × (5 - 2) + 3 × 2

 

우선순위순으로 연산

 

1. 괄호

3 + 2 × 3 + 3 × 2

 

2. 곱하기

3 + 6 + 6

 

3. 더하기, 빼기

3 + 6 + 6 = 15

 

예제입력 1.

 

1. 입력되는 정보들을 저장합니다.

 

N=9

연산식 : 3 + 8 × 7 - 9 × 2

 

2. 괄호를 놓는 모든 경우를 탐색하여 식의 값을 구합니다.

 

나올수 있는 연산식

 

 3 + 8 × 7 - 9 × 2

1. 괄호 X

2. 곱하기 : 3 + 56 - 18

3. 더하기, 빼기 : 3 + 56 - 18 = 41

 

 (3 + 8) × 7 - 9 × 2

1. 괄호 : 11 × 7 - 9 × 2

2. 곱하기 : 77 - 18

3. 더하기, 빼기 : 77 - 18 = 59

 

 (3 + 8) × (7 - 9) × 2

1. 괄호 : 11 × (-2) × 2

2. 곱하기 : -44

3. 더하기, 빼기 X : -44

 

 (3 + 8) × 7 - (9 × 2)

1. 괄호 : 11 × 7 - 18

2. 곱하기 : 77 - 18

3. 더하기, 빼기 : 77 - 18 = 59

 

 3 + (8 × 7) - 9 × 2

1. 괄호 : 3 + 56 - 9 × 2

2. 곱하기 : 3 + 56 - 18

3. 더하기, 빼기 : 3 + 56 - 18 = 41

 

 3 + (8 × 7) - (9 × 2)

1. 괄호 : 3 + 56 - 18

2. 곱하기 : 3 + 56 - 18

3. 더하기, 빼기 : 3 + 56 - 18 = 41

 

 3 + 8 × (7 - 9) × 2

1. 괄호 : 3 + 8 × (-2) × 2

2. 곱하기 : 3 + (-32)

3. 더하기, 빼기 :  3 + (-32) = -29

 

 3 + 8 × 7 - (9 × 2)

1. 괄호 :  3 + 8 × 7 - 18

2. 곱하기 : 3 + 56 - 18

3. 더하기, 빼기 :  3 + 56 - 18 = 41

 

 

3. 모든 경우 탐색 후 식의 최대값을 결과로 출력합니다.

 

 (3 + 8) × 7 - 9 × 2 = 59

최대값 59를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• search함수를 괄호를 놓는 모든 경우를 탐색합니다.
• 모든 경우 탐색 후 식의 최대값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 괄호를 놓는 모든 경우를 탐색합니다.
• setCalculation함수는 우선순위가 높은 괄호와 곱하기를 먼저 계산하여 더하기와 빼기로 된 식을 만듭니다.
• start함수는 더하기와 빼기로 구성된 식의 결과를 구합니다.
• cal함수는 각 연산자에 따른 피연산자들을 계산합니다.

 

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

public class Main {
    static int N, answer = Integer.MIN_VALUE;
    static String input;		//입력되는 연산식 저장
    static boolean[] bracket;	//괄호 확인 함수
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        bracket = new boolean[N];
        input = br.readLine();	//입력된 식 저장
        //식의 길이가 1개일 때 해당 값이 최대값
        if(input.length()==1)		
            answer = Character.getNumericValue(input.charAt(0));
        else	//식의 길이 1개 이상일 때 괄호 놓는 모든 경우 탐색
            search(0);
        bw.write(answer + "");	//최대값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //식의 괄호를 놓는 모든 경우 탐색
    static void search(int depth){
        if(depth==N+1){		//식 완성시.
            start(setCalculation());	//해당 식 계산하기
            return;
        }
        //식의 처음에 괄호를 추가할 때
        if(depth==0){
            bracket[depth]=true;
            search(depth+2);
            bracket[depth]=false;
        }else{	//처음이후 괄호를 추가할 때
            //중첩되면 안되기 때문에 이전 피연산자에 괄호가 존재하는지 확인
            if(!bracket[depth-2] && depth!=N-1){
                bracket[depth] = true;
                search(depth+2);
                bracket[depth] = false;
            }
        }
        search(depth+2);		//괄호 추가하지 않을 때
    }
    //우선순위 기준으로 괄호와 곱하기를 진행하여 더하기와 뺄셈으로 된 식 구하는 함수
    static ArrayList<String> setCalculation(){
        int index=0;
        ArrayList<String> list = new ArrayList<>();	//식 저장 함수
        while(index<N){
            char temp = input.charAt(index);
            if(temp == '+' || temp =='-'){
                list.add(String.valueOf(temp));
            }else if(temp == '*'){		//곱하기일 때는 연산 진행
                int n1 = Integer.parseInt(list.get(list.size()-1));
                int n2;
                if(bracket[index+1]){	//피연산자가 괄호가 있을 때 괄호 먼저 계산
                    int t1 = Character.getNumericValue(input.charAt(index+1));
                    int t2 = Character.getNumericValue(input.charAt(index+3));
                    n2 = cal(t1, t2, input.charAt(index+2));
                    index+=3;
                }else{		//피연산자가 괄호가 없을 때
                    n2 = Character.getNumericValue(input.charAt(index+1));
                    index++;
                }
                list.set(list.size()-1,String.valueOf(cal(n1, n2, temp)));
            }else{	//피연산자(숫자)일 때
                if(bracket[index]){	//숫자의 괄호가 있으면 해당 괄호에 연산 계산
                    int n1 = Character.getNumericValue(temp);
                    int n2 = Character.getNumericValue(input.charAt(index+2));
                    list.add(String.valueOf(cal(n1, n2, input.charAt(index+1))));
                    index+=2;
                }else		//숫자의 괄호가 없으면 바로 식의 저장
                    list.add(String.valueOf(temp));
            }
            index++;
        }
        return list;
    }
    //더하기와 빼기로 구성된 식 계산하는 함수
    static void start(ArrayList<String> list){
        int result = Integer.parseInt(list.get(0));
        for(int i=1;i<list.size();i+=2)
            result = cal(result, Integer.parseInt(list.get(i+1)),list.get(i).charAt(0));

        answer = Math.max(answer, result);
    }
    //연산자에 따른 피연산자들 계산하는 함수
    static int cal(int n1, int n2, char operation){
        if(operation == '+')		//덧셈
            return n1+n2;
        else if(operation == '-')	//뺄셈
            return n1-n2;
        else	//곱셈
            return n1*n2;
    }
}