[백준/Java] 15649번 N과 M (1)

-Code

import java.io.*;
import java.util.*;

public class Main {
    static Deque<Integer> nums = new ArrayDeque<>();
    static StringBuilder answer = new StringBuilder();

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        backtracking(0, 1, n, m);

        System.out.println(answer);
    }

    private static void backtracking(int depth, int start, int length, int checkCnt) {
        // 깊이 (현재 저장 숫자)와 고르는 횟수가 같으면 값 저장
        if (depth == checkCnt) {
            answerAppend();
            return;
        }
        // 최대 수까지 돌면서 값을 저장
        for (int i = 1; i <= length; i++) {
            if (!nums.contains(i)){
                nums.addLast(i);
                backtracking(depth + 1, i + 1, length, checkCnt);
                nums.pollLast();
            }
        }
    }
    // 결과 저장
    private static void answerAppend() {
        for (int num : nums) {
            answer.append(num).append(" ");
        }
        answer.append("\n");
    }
}

어제 힌트를 얻고 오늘 다시 혼자서 풀어보았습니다. 통과를 했지만 contains가 O(n)이 됨을 통과되고 인지했고 visited를 이용하는게 검사로직에 O(1)이 되어서 성능적으로 더 좋아 아래와 같이 변경했습니다.

import java.io.*;
import java.util.*;

public class BOJ15649 {
    static Deque<Integer> nums = new ArrayDeque<>();
    static StringBuilder answer = new StringBuilder();
    static boolean[] visited;

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        visited = new boolean[n + 1];

        backtracking(0, n, m);

        System.out.println(answer);
    }

    private static void backtracking(int depth, int length, int checkCnt) {
        // 깊이 (현재 저장 숫자)와 고르는 횟수가 같으면 값 저장
        if (depth == checkCnt) {
            answerAppend();
            return;
        }
        // 최대 수까지 돌면서 값을 저장
        for (int i = 1; i <= length; i++) {
            if (!visited[i]){
                visited[i] = true;
                nums.addLast(i);
                backtracking(depth + 1, length, checkCnt);
                nums.pollLast();
                visited[i] = false;
            }
        }
    }
    // 결과 저장
    private static void answerAppend() {
        for (int num : nums) {
            answer.append(num).append(" ");
        }
        answer.append("\n");
    }
}