백준 7490 0 만들기

import javax.naming.ldap.PagedResultsResponseControl;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Make_Zero {
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            N = Integer.parseInt(br.readLine());
            dfs(1,new char[N]);
            System.out.println();
        }
    }
    public static void dfs(int count, char[] arr){
        if(count==N){
            if(result(arr)){
                System.out.print(1);
                for (int i = 1; i < N; i++) {
                    System.out.print(arr[i]);
                    System.out.print(i+1);
                }
                System.out.println();
            }
            return;
        }
        arr[count] = ' ';
        dfs(count+1, arr);
        arr[count] = '+';
        dfs(count+1, arr);
        arr[count] = '-';
        dfs(count+1, arr);
    }
    public static boolean result(char[] arr){
        StringBuilder sb = new StringBuilder();
        sb.append('+').append(1);
        for (int i = 1; i < N; i++) {
            sb.append(arr[i]).append(i+1);
        }
        StringBuilder temp = new StringBuilder();
        for (int i = 0; i < 2*N; i++) {
            String  str = sb.substring(i,i+2);
            if(str.charAt(0)==' '){
                temp.append(str.charAt(1));
            }
            else {
                temp.append(str);
            }
            i++;
        }
        int sum =0;
        String s = String.valueOf(temp);
        StringTokenizer st = new StringTokenizer(s,"+|-",true);
        while (st.hasMoreElements()){
            String t = st.nextToken();
            if(t.equals("+")){
                sum += Integer.parseInt(st.nextToken());
            }
            else {
                sum -= Integer.parseInt(st.nextToken());
            }
        }
        if(sum == 0){
            return true;
        }
        return false;
    }
}

풀이방법

1. 1부터 N까지의 숫자를 노드로 하고, 각 노드마다 + , - , 3가지 연산을 하는 dfs를 설계한다.
2. N까지 dfs를 통해 탐색하는데 탐색시 노드마다 배열에 연산을 담는다.
3. 연산 배열을 result 함수에 넘기고, 배열 순서대로 stringbuilder를 통해 문자열을 만든다.
4. 만든 문자열을 공백을 제거하여 다시 새로운 문자열로 만든다.
5. stringtokenizer를 통해 "+,-"를 구분자로 하여, t에 담는다.
6. +,-도 토큰으로 담기기 때문에 토큰에 해당하는 연산을하여 sum에 담는다.
7. sum이 0일때만 true를 리턴한다.
8. result 함수가 true를 리턴했다면, 해당 배열을 숫자와 함께 출력한다.

후기

dfs로 해야겠다는 생각까지는 들었는데 공백처리에서 막혀서 못풀었다.
연산을 하면서 dfs를 해나가는 풀이를 설계했는데, 그렇게 하지말고 전체 식을 만들어놓고 int형으로 바꿔 연산을 진행하는 풀이로 해야한다.
구분자를 포함하는 메서드가 필요했는데
StringTokenizer(문자열,구분자,토큰포함여부)로 하는 법을 새로 배웠다.
유용하게 쓰일것 같다.

다음에 다시 풀어볼만한 문제인것 같다.