[백준] 16637번 : 괄호 추가하기 Gold3(골드3) - JAVA[자바]

[Gold III] 괄호 추가하기 - 16637

문제 링크

성능 요약

메모리: 11780 KB, 시간: 80 ms

분류

브루트포스 알고리즘, 구현

제출 일자

2024년 2월 5일 20:26:53

문제 설명

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 2³¹보다 작고, -2³¹보다 크다.

 

접근 방법

1. 괄호를 추가할수도 아예 안할수도 있다. 모든 경우의 수를 따져야한다. 

2. 만약 현재 위치에 괄호를 친다면 다음 위치에는 괄호를 체크할 수 없다.

3. depth가 연산자의 개수만큼 괄호를 체크한다면 계산하는 로직을 실행한다.

4. 계산하는 과정에 있어서 괄호를 먼저 처리한 후 연산자와 큐에 다시 넣어준다.

 

괄호의 조합을 얻는 메서드

// 괄호의 조합을 짜주는 메서드
    private static void combinationOper(int depth) {
        // 연산자 길이만큼 확인 했다면 계산 로직
        if (depth == operLen) {
            // 원본이 아닌 복사본을 넘겨준다.
            calc(Arrays.copyOf(num, numLen));
            return;
        }

        // 0번째거나 -1번째를 방문 안했다면 true 처리 후 재귀호출
        if (depth == 0 || !visit[depth - 1]) {
            visit[depth] = true;
            combinationOper(depth + 1);
            visit[depth] = false;
        }

        // 괄호 안 씌운 것도 넘겨줌
        combinationOper(depth + 1);
    }

 

계산을 실행하는 메서드

 // 계산하는 로직
    private static void calc(int[] arr) {
        // 순서대로 계산해주기 위해서 큐를 사용한다.
        Queue<Integer> num = new LinkedList<>();
        Queue<Character> oper = new LinkedList<>();
        // 연산자 길이 확인
        for (int i = 0; i < operLen; i++) {
            // 괄호가 씌어졌다면 i + 1값에 저장
            if (visit[i]) {
                arr[i + 1] = match(arr[i], arr[i + 1], op[i]);
            } else {
                // 괄호가 씌어지지 않았다면 연산자 큐에 추가
                oper.add(op[i]);
            }
        }

        // 값들을 모두 넣어준다. 마지막 값은 따로 넣어준다.
        for (int i = 0; i < numLen - 1; i++) {
            if (!visit[i]) {
                num.add(arr[i]);
            }
        }
        num.add(arr[numLen - 1]);

        // 초기값을 result에 넣어놓음
        int result = num.poll();
        while (!num.isEmpty()) {
            // 다음 피연산자를 num 큐에서 빼준다.
            int nextValue = num.poll();
            // 다음 연산자를 oper 큐에서 빼준다.
            char nextOp = oper.poll();
            result = match(result, nextValue, nextOp);
        }

        // answer보다 크다면 갱신
        if (answer < result) answer = result;
    }

 

연산자 매핑 메서드

// 연산자에 매핑하여 계산해주는 로직
    private static int match(int a, int b, char op) {
        if (op == '+') {
            return a + b;
        } else if (op == '-') {
            return a - b;
        } else {
            return a * b;
        }
    }

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    // 숫자를 저장하는 배열
    static int[] num;
    // 연산자를 저장하는 배열
    static char[] op;
    // 방문 처리 배열
    static boolean[] visit;
    static int answer = Integer.MIN_VALUE, numLen, operLen;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // 숫자 배열의 길이는 n / 2 + 1이다.
        numLen = n / 2 + 1;
        operLen = n / 2;
        num = new int[numLen];
        op = new char[operLen];
        visit = new boolean[operLen];

        String input = br.readLine();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                num[i / 2] = input.charAt(i) - '0';
            } else {
                op[i / 2] = input.charAt(i);
            }
        }

        combinationOper(0);

        System.out.println(answer);
    }

    // 괄호의 조합을 짜주는 메서드
    private static void combinationOper(int depth) {
        // 연산자 길이만큼 확인 했다면 계산 로직
        if (depth == operLen) {
            // 원본이 아닌 복사본을 넘겨준다.
            calc(Arrays.copyOf(num, numLen));
            return;
        }

        // 0번째거나 -1번째를 방문 안했다면 true 처리 후 재귀호출
        if (depth == 0 || !visit[depth - 1]) {
            visit[depth] = true;
            combinationOper(depth + 1);
            visit[depth] = false;
        }

        // 괄호 안 씌운 것도 넘겨줌
        combinationOper(depth + 1);
    }

    // 계산하는 로직
    private static void calc(int[] arr) {
        // 순서대로 계산해주기 위해서 큐를 사용한다.
        Queue<Integer> num = new LinkedList<>();
        Queue<Character> oper = new LinkedList<>();
        // 연산자 길이 확인
        for (int i = 0; i < operLen; i++) {
            // 괄호가 씌어졌다면 i + 1값에 저장
            if (visit[i]) {
                arr[i + 1] = match(arr[i], arr[i + 1], op[i]);
            } else {
                // 괄호가 씌어지지 않았다면 연산자 큐에 추가
                oper.add(op[i]);
            }
        }

        // 값들을 모두 넣어준다. 마지막 값은 따로 넣어준다.
        for (int i = 0; i < numLen - 1; i++) {
            if (!visit[i]) {
                num.add(arr[i]);
            }
        }
        num.add(arr[numLen - 1]);

        // 초기값을 result에 넣어놓음
        int result = num.poll();
        while (!num.isEmpty()) {
            // 다음 피연산자를 num 큐에서 빼준다.
            int nextValue = num.poll();
            // 다음 연산자를 oper 큐에서 빼준다.
            char nextOp = oper.poll();
            result = match(result, nextValue, nextOp);
        }

        // answer보다 크다면 갱신
        if (answer < result) answer = result;
    }

    // 연산자에 매핑하여 계산해주는 로직
    private static int match(int a, int b, char op) {
        if (op == '+') {
            return a + b;
        } else if (op == '-') {
            return a - b;
        } else {
            return a * b;
        }
    }
}