💜 백준 7490. 0 만들기 JAVA

1. 문제 설명

0 만들기 문제 링크

3~9까지 수가 주어지는데, 그 사이 사이에 + 혹은 - 혹은 두 수 붙이기를 사용하여, 총 합을 0으로 만들어라.

2. 푸는 원리

• 이런 문제는 일일히 char로 분할하여 가지고 있는 것보다, String으로 한번에 가지고 있다가 StringTokenizer로 푸는 것이 좋다는 것을 알았다.

(1) DFS를 돌린다. (-> String에 다음 depth의 값을 추가하는 식)

(2) 한번은 두 수 사이에 +를 넣고, 한번은 두 수 사이에 -를 넣고 한번은 두 수 사이에 공백을 넣고 경우를 진행한다.

(3) 마지막 수까지 String 문자열에 쌓이면, cal이란 이름의 함수에 넣어서 계산한다.

(4) cal의 역할은 다음과 같다.

​ a. 공백인 부분을 합쳐서 하나의 수로 만든다.

​ b. +나 - 라는 문자가 나오면 뒤에 수를 Int로 바꿔서 진짜 더하거나 뺸다.

​ c. 이렇게 해서 총합이 0이면 true, 아니면 false를 내뱉는다.

3. 코드 분석

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
* 7490번 0 만들기
* */


public class Main {


    static int N;
    static ArrayList<String> ans;
    static String [] op = {"+", "-", " "};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());

        for (int tc = 0; tc < T; tc++) {
            N = Integer.parseInt(br.readLine());
            ans = new ArrayList<>();
            dfs(1,"1");

            // 정렬 필요
            Collections.sort(ans);

            for (String temp : ans){
                System.out.println(temp);
            }
            System.out.println();

        }


    }


    // 1. dfs -> depth 마다 연산자 + 다음 숫자 조합을 추가하여 다음으로 넘어간다.
    public static void dfs (int depth, String express) {

        if(depth == N) {

            // 연산자 + 다음 숫자 조합이라서,
            if(cal(express)){
                ans.add(express);
            };

            return;
        }

        for (int i = 0; i < op.length; i++) {
            dfs(depth+1, express+op[i]+(depth+1));
        }

    }

    // 2. cal -> 기저 조건에서 쓰이는 함수, [StringTokenizer]로 잘라서 변환해서 계산한다.
    public static boolean cal (String express) {

        // 2-1) 공백 제거, 숫자 붙이기
        String s = express.replaceAll(" ", "");

        // 2-2) [StringTokenizer]로 자르기
        StringTokenizer st = new StringTokenizer(s, "+|-", true);


        int ans = Integer.parseInt(st.nextToken());

        // 2-3) 자른 대로 더해 넣기
        while (st.hasMoreElements()) {

            String temp = st.nextToken();

            if(temp.equals("+")){
                ans += Integer.parseInt(st.nextToken());
            }
            if(temp.equals("-")){
                ans -= Integer.parseInt(st.nextToken());
            }
        }
        return ans == 0;
    }
}