백준 7490번 - 0 만들기

문제

7490번: 0 만들기

풀이

오름차순 수열(1 2 3 … N 의 형태)이 주어지면 수열 사이 숫자에 + , - , 공백중 하나를 삽입하여 수식을 만들고 그 계산 결과가 0인 경우만을 구하여 ASCII 순서에 따라 출력해야 한다. 경우의 수를 구해야 한다는 측면에서 백트래킹을 활용하여 접근하였다. 또한 현재까지의 계산 결과가 음수더라도 뒤에 + 를 추가하여 0으로 수렴할 수 있으며, 테스트 케이스 개수와 $N$의 최대값이 크지 않다는 점에서 모든 경우의 수를 다 계산하는 방향으로 로직을 구성할 수 있을 것이라 생각했다.

로직은 다음 네 부분으로 나뉘어진다.

• 수식 문자열에서 연산자를 추출하는 로직
• 수식 문자열에서 숫자를 추출하는 로직
• 수식 문자열을 계산하는 로직
• dfs 를 진행하며 연산자의 조합을 구하고, 수식 문자열을 형성하여 계산 결과가 0인 경우 정답으로 저장하는 로직

수식 문자열에서 연산자와 숫자를 추출하는 로직의 경우 해당 데이터들을 ArrayDeque 에 담아 반환토록 하였다. 처음에는 Stack 을 이용하였는데 덱을 활용하는 것이 로직을 더 직관적으로 구성할 수 있는 면이 있어 자료구조를 바꾸었다.

dfs 에서는 클래스 필드 스택에 현재까지의 연산자 조합을 저장하는데, 탐색 진행 과정에서 모든 경우의 수를 구할 수 있도록 스택에 연산자를 넣고 dfs 다음 depth를 계산한 후 넣은 연산자를 빼도록 로직을 구성했다.

테스트 케이스 $T$의 최대값이 10이고, $N$의 최대값이 9일 때 가능한 최대 연산자 경우의 수는 $3^{N-1}=3^8=6,561$이므로 전체 로직의 최악의 시간복잡도는 $O(T3^{N-1})=10\times 3^8=10\times 6561$이다. 따라서 제한 시간 1초를 무난히 통과할 수 있다.

코드

import static java.lang.Integer.parseInt;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
    static int N;
    static Stack<Character> operators = new Stack<>();
    static char[] ops = {'+', '-', ' '};
    static List<String> answers = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            N = parseInt(br.readLine());
            dfs(0);
            Collections.sort(answers);
            answers.forEach(answer -> sb.append(answer).append("\n"));
            sb.append("\n");
            operators.clear();
            answers.clear();
        }

        System.out.print(sb);
        br.close();
    }

    static void dfs(int depth) {
        if (depth == N - 1) {
            StringBuilder sb = new StringBuilder();
            List<Character> ops = operators.stream()
                    .collect(Collectors.toList());
            int num = 1;
            sb.append(num++);
            for (Character op : ops) {
                sb.append(op)
                        .append(num++);
            }

            int calculateResult = calculateExp(sb.toString());
            if (calculateResult == 0) {
                answers.add(sb.toString());
            }

            return;
        }

        for (char ch : ops) {
            operators.push(ch);
            dfs(depth + 1);
            operators.pop();
        }
    }

    static int calculateExp(String exp) {
        String result = exp.replace(" ", "");
        ArrayDeque<Integer> operands = getOperands(result);
        ArrayDeque<Character> operators = getOperators(result);

        while (!operators.isEmpty()) {
            Integer num1 = operands.poll();
            Integer num2 = operands.poll();
            Character op = operators.poll();

            switch (op) {
                case '+':
                    operands.offerFirst(num1 + num2);
                    break;
                case '-':
                    operands.offerFirst(num1 - num2);
                    break;
            }
        }

        return operands.pop();
    }

    static ArrayDeque<Integer> getOperands(String exp) {
        StringTokenizer st = new StringTokenizer(exp, "+-");
        ArrayDeque<Integer> operands = new ArrayDeque<>();
        while (st.hasMoreTokens()) {
            operands.offer(Integer.valueOf(st.nextToken()));
        }
        return operands;
    }

    static ArrayDeque<Character> getOperators(String exp) {
        ArrayDeque<Character> operators = new ArrayDeque<>();
        exp.chars().filter(ch -> !Character.isDigit(ch))
                .forEach(ch -> operators.offer((char) ch));
        return operators;
    }
}