[백준 7490번] 0 만들기 - java

문제 설명

1. 테스트 케이스 개수가 주어진다.
2. N이 주어지면, 1부터 N 까지 오른차순 수열이 있다.
3. '+' '-' ' ' 이렇게 삽입된다. 
4. 이렇게해서 1 ~ N 까지의 수식이 완성되었을 때 그 수식의 결과가 0이 되면 그걸 출력한다.
5. 참고로 ASCII 순서에 따라 출력한다.

풀이 과정

1. BF + DFS문제이다.
2. String에다가 모든 수식이랑 숫자를 다 DFS로 찾도록 구하고 그걸 처리하면 된다.
3. 계산하는 방법은 공백 없이 문자를 이어주고(이러면 알아서 붙음) 수식 위치를 구한 후에 숫자를 뽑아서 이 수식대로 처리해주면 된다.
4. 0이 되면 출력
5. 참고로 ASCII 순서에 따라 DFS처리하면 간단하다 ' ' -> '+' -> '-' 순서임.

코드

import java.util.*;

public class Main {
    private static int N;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = Integer.parseInt(sc.nextLine());

        while(T-->0) {
            N = sc.nextInt();
            validater(1, "1");
            System.out.println();
        }
    }

    private static void validater(int now, String str) {
        if (now == N) {
            calculater(str);
            return;
        }
        
        now++;
        
        validater(now, str + " " + now);
        validater(now, str + "+" + now);
        validater(now, str + "-" + now);
    }

    private static void calculater(String input) {
        String str = input.replace(" ", "");
        LinkedList<Character> q = new LinkedList<>();
        for(int i=0; i<str.length(); i++) {
            char del = str.charAt(i);
            if (del == '+') {
                q.add('+');
            } else if (del == '-') {
                q.add('-');
            }
        }
        String numStrList[] = str.split("[+-]");
        int num = Integer.parseInt(numStrList[0]);
        for(int i=1; i<numStrList.length; i++) {
            int now = Integer.parseInt(numStrList[i]);
            if (q.remove() == '+') {
                num += now;
            } else {
                num -= now;
            }
        }
        if (num == 0) System.out.println(input);
    }
}