[BOJ/Java] 16637. 괄호 추가하기

[BOJ/Java] 16637. 괄호 추가하기

16637번: 괄호 추가하기

---

문제 해석

이 문제에서는 N개의 문자(숫자와 연산자)로 구성된 수식이 주어지며, 괄호를 적절히 추가하여 수식의 결과를 최대로 만드는 값을 찾아야 한다. 괄호는 중첩할 수 없으며, 한 번에 하나의 연산만을 포함할 수 있다.

풀이 과정

• 변수 선언 및 입력 처리: N은 수식의 길이, arr은 주어진 문자열을 담는 배열이다.
• 재귀 함수 설계: recursive 함수를 통해 괄호를 추가할 수 있는 모든 위치를 탐색하며, 각 경우에 대한 계산 결과를 반환한다. 함수는 현재 인덱스(idx)와 이전까지의 계산 결과(res)를 매개변수로 받는다.
• 조건 분기: idx가 N 이상이면 계산이 완료된 것으로 판단, 현재 결과를 최대 결과(ans)와 비교하여 갱신한다. idx + 2 < N이면, 연산자 다음 위치에 괄호를 추가할 수 있음을 의미한다.
• 계산 함수 cal: 두 수와 연산자를 매개변수로 받아 계산 결과를 반환한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No16637;

import java.io.*;

public class Main {
    private static int N;                  // 수식의 길이
    private static char[] arr;             // 수식을 문자 배열로 저장
    private static int ans = Integer.MIN_VALUE;  // 최대 결과값을 저장할 변수, 최소값으로 초기화

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());   // 수식 길이 입력 받기

        String s = br.readLine();              // 수식 입력 받기
        arr = new char[N];
        for (int i = 0; i < N; i++) {          // 수식을 char 배열에 저장
            arr[i] = s.charAt(i);
        }

        recursive(2, arr[0] - '0');            // 재귀 함수 호출

        sb.append(ans);                        // 결과값 출력 준비
        bw.write(sb.toString());               // 결과값 출력
        bw.flush();
        bw.close();
    }

    private static void recursive(int idx, int res) {
        if (idx >= N) {
            ans = Math.max(ans, res);  // 결과값 갱신
            return;
        }

        // 연산자 다음에 괄호를 추가하여 먼저 계산하는 경우
        if (idx + 2 < N) recursive(idx + 4, cal(res, arr[idx - 1], cal(arr[idx] - '0', arr[idx + 1], arr[idx + 2] - '0')));
        // 현재 위치에서 바로 계산하는 경우
        recursive(idx + 2, cal(res, arr[idx - 1], arr[idx] - '0'));
    }

    private static int cal(int x, char op, int y) {
        switch (op) {  // 연산자에 따른 계산 수행
            case '+': return x + y;
            case '-': return x - y;
            case '*': return x * y;
        }
        return -1;  // 에러 처리, 불가능한 상황
    }
}

시간 복잡도 분석

재귀적 탐색을 통해 괄호를 추가하는 모든 경우의 수를 계산하므로, 대략적인 시간 복잡도는 𝑂(2^(𝑁/2))가 될 수 있다. 이는 각 연산자마다 괄호를 추가하거나 추가하지 않는 선택을 할 수 있기 때문이다.

느낀점

이 문제는 재귀적인 접근과 백트래킹을 사용하여 모든 가능한 경우의 수를 탐색하는 방식으로 접근하였다. 괄호를 적절히 추가하여 계산 결과를 최대로 만드는 문제의 특성상, 브루트 포스 접근이 효과적이었다. 문제를 푸는 동안 재귀 함수의 설계와 조건 분기에 대한 이해가 중요하다는 것을 느꼈다.