BOJ(10597) - 순열장난 (JAVA)

https://www.acmicpc.net/problem/10597

10597번: 순열장난

 

• 백트래킹 탐색 문제이다.
• 처음에는 주어진 입력 문자열을 String.IndexOf를 사용하여 완탐했으나 10이 넘어가는 시점에서 탐색 개수가 기하급수 적으로 늘어나 시간 초과를 받았다.
• 문제에서 주어진 조건으로 최대 N!이 50이 넘지 않기에 1~ 2 길이를 이용하여 만들 수 있는 모든 문자열을 검색하는 것으로 바꾸었다.

 

처음부터 시작하여 문자열 길이 1,2로 탐색하는 경우

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;


public class Main {
    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static String word;
    private static boolean[] visit;
    private static int countOfNumbers;
    private static List<Node> indexes = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        word = br.readLine();

        if (word.length() > 9) {
            countOfNumbers = (word.length() - 9) / 2 + 9;
        } else {
            countOfNumbers = word.length();
        }

        visit = new boolean[countOfNumbers + 1];

        dp(0, word, 0);
    }

    private static void dp(int depth, String word, int currentIndex) {
        if (depth == countOfNumbers) {
            //1 ~ N 까지 탐색 했는지 확인 
            for (int i = 1; i < visit.length; i++) {
                if (!visit[i]) return;
            }

            List<Node> collect = indexes.stream().sorted().collect(Collectors.toList());
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < collect.size(); i++) {
                builder.append(collect.get(i).number);
                if (i < collect.size() - 1) {
                    builder.append(' ');
                }
            }

            System.out.println(builder);
            System.exit(0);
            return;
        }

        for (int i = 1; i <= 2; i++) {
            //길이를 초과하면 탐색 종료
            if (currentIndex + i > word.length()) continue;
            int number = Integer.parseInt(word.substring(currentIndex, currentIndex + i));
            //주어진 숫자보다 클 경우 탐색 종료
            if (number > countOfNumbers) continue;

            //앞에서 이미 방문 했을 경우 탐색 종료 
            if (visit[number]) continue;

            indexes.add(new Node(number, currentIndex));
            visit[number] = true;
            dp(depth + 1, word, currentIndex + i);
            visit[number] = false;
            indexes.remove(indexes.size() - 1);
        }
    }

    static class Node implements Comparable<Node> {
        public int number;
        public int index;

        public Node(int number, int index) {
            this.number = number;
            this.index = index;
        }

        @Override
        public int compareTo(Node other) {
            return this.index - other.index;
        }
    }
}