BOJ_15649 : N과 M (1)

👉 문제링크

15649번: N과 M (1)

---

---

🔸 문제 분석 🔸

• 1 부터 N 까지의 수 중에서 M개를 고르는 경우의 수를 나열한다.
  • 순서가 있는 수열
  • 수가 중복되서 출력되면 안됨
• 재귀 방식으로 백트래킹을 적용해 풀이한다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    private static void dfs(ArrayList<Integer> arr, int n, int d) {
        if (arr.size() == d) {
            for (int i : arr) {
                System.out.print(i + " ");
            }
            System.out.println("");
            return;
        }

        for (int i = 1; i <= n; i++) {
            if (!arr.contains(i)) {
                arr.add(i);
                dfs(arr, n, d);
                arr.remove(arr.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ArrayList<Integer> arr = new ArrayList<>();

        dfs(arr, n, m);
    }
}

🔸 코드 해석 🔸

• ArrayList형 arr 배열에 m개의 값을 선택해 넣고, 가득차면 출력한다.
• 이미 들어간 간 값은 포함되면 안되므로 arr.contains()로 확인한다.

---

🔸 end 🔸

• contains()로 확인하면 효율이 좋지 않을거라 생각하고 boolean배열 visit을 만들어서 체크해봤지만 더 256ms 더 느려지는것으로 나타났다.