BOJ7490 0 만들기 java

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

이 문제의 핵심은 재귀와 replaceAll 이다.

Key [1]

숫자 리스트와 연산자 리스트를 분리하여 모든 경우의 수를 계산한다.

[재귀를 사용]

근거는? 자연수 범위가 3이상 9이하이므로 완전 탐색이 가능하다.

연산자의 경우의 수를 먼저 구해줬다.

    private static void dfs(int count, int N, char[] operations) {
        if (count == N) {
            for (int i = 1; i <= N - 1; i++) {
                sb.append(operations[i]);
            }
            sb.append("\\n");
            return;
        }
        operations[count] = ' ';
        dfs(count + 1, N, operations);
        operations[count] = '+';
        dfs(count + 1, N, operations);
        operations[count] = '-';
        dfs(count + 1, N, operations);
    }

Key [2]

공백 처리가 애매할 수 있는데 replaceAll로 처리하였다.

expression = expression.replaceAll(" ", "");

그 뒤로 연산자와 숫자 리스트를 분리해주었다.

String[] numbers = expression.split("[\\\\+-]");
expression = expression.replaceAll("[0-9]", "");
String[] operations = expression.split("");

전체 코드

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

public class Main {
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.valueOf(br.readLine());
        for (int t = 0; t < T; t++) {
            sb = new StringBuilder();
            int N = Integer.valueOf(br.readLine());
            int[] numbers = new int[N + 1];
            for (int i = 1; i <= N; i++) {
                numbers[i] = i;
            }
            char[] operations = new char[N + 1];
            dfs(1, N, operations);
            String[] operationList = sb.toString().split("\\n");
            for (String operation : operationList) {
                String expression = printExpression(operation);
                if (checkSumZero(expression)) {
                    System.out.println(expression);
                }
            }
            System.out.println();
        }
    }

    private static String printExpression(String operation) {
        StringBuilder sb = new StringBuilder();
        int number = 1;
        sb.append(number++);
        String[] operations = operation.split("");
        for (String op : operations) {
            sb.append(op);
            sb.append(number++);
        }
        return sb.toString();
    }

    private static boolean checkSumZero(String expression) {
        expression = expression.replaceAll(" ", "");
        String[] numbers = expression.split("[\\\\+-]");
        expression = expression.replaceAll("[0-9]", "");
        String[] operations = expression.split("");
        int sum = Integer.valueOf(numbers[0]);
        int index = 1;
        for (String operation : operations) {
            if (operation.equals("+")) {
                sum += Integer.valueOf(numbers[index++]);
            } else if(operation.equals("-")) {
                sum -= Integer.valueOf(numbers[index++]);
            } else {
                continue;
            }
        }

        return sum == 0;
    }

    private static void dfs(int count, int N, char[] operations) {
        if (count == N) {
            for (int i = 1; i <= N - 1; i++) {
                sb.append(operations[i]);
            }
            sb.append("\\n");
            return;
        }
        operations[count] = ' ';
        dfs(count + 1, N, operations);
        operations[count] = '+';
        dfs(count + 1, N, operations);
        operations[count] = '-';
        dfs(count + 1, N, operations);
    }

}