7490 0만들기 (Java)

0 만들기

문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

풀이

모든 경우의수를 만들어 0이 되는 경우를 답에 추가한다.
모든 경우의 수 => 백트레킹을 이용하여 구현한다.
다만 이 문제에서 어려운 점은 String으로 이루어진 식을 계산하는 것이다.
나는 String에서 replaceAll함수로 공백을 삭제하고 split함수로 +, -를 나누어 정수값들을 구했다.
그리고 연산자에 맞춰 계산을 진행했다.

코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main{

    static StringBuilder sb = new StringBuilder();
    static List<String> list = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            String s = "1";
            list = new ArrayList<>();
            backTracking(n, 2, s);
            Collections.sort(list);
            for(String e : list){
                sb.append(e).append("\n");
            }
            sb.append("\n");
        }


        System.out.println(sb);

    }



    static void backTracking(int n, int now, String s) {
        if (now > n) {

            if (cal(s)) {
                list.add(s);

            }
            return;
        }
        s += "+";
        s += now;
        backTracking(n, now + 1, s);
        s = s.substring(0, s.length() - 2);

        s += "-";
        s += now;
        backTracking(n, now + 1, s);
        s = s.substring(0, s.length() - 2);

        s += " ";
        s += now;
        backTracking(n, now + 1, s);
        s = s.substring(0, s.length() - 2);
    }

    static boolean cal(String s){
        String temp = s.replaceAll(" ", "");
        String[] num  = temp.split("\\+|\\-");
        int idx = 1;
        int sum = Integer.parseInt(num[0]);
        for (int i = 0; i < temp.length(); i++) {
            char c = temp.charAt(i);
            if (c == '+') {

                sum += Integer.parseInt(num[idx++]);
            } else if (c == '-') {

                sum -= Integer.parseInt(num[idx++]);
            }


        }


        return sum == 0 ? true : false;
    }
}