BOJ_15654 : N과 M (5)

👉 문제링크

15654번: N과 M (5)

---

---

🔸 문제 분석 🔸

• n개의 수에서 m개를 고르는 경우의 수를 출력한다.
• 고른 수는 중복되면 안된다.
• 경우의 수들은 사전 순으로 증가하는 순서로 출력한다.

🔸 코드 🔸

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    static ArrayList<Integer> arr, pick;
    static int n, m;

    private static void dfs() {
        if (pick.size() == m) {
            for (int i : pick) {
                System.out.print(arr.get(i) + " ");
            }
            System.out.println("");
        }
        for (int i = 0; i < n; i++) {
            if (!pick.contains(i)) {
                pick.add(i);
                dfs();
                pick.remove(pick.size()-1);
            }
        }
    }

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

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

        for (int i = 0; i < n; i++) {
            arr.add(sc.nextInt());
        }

        Collections.sort(arr);

        dfs();
    }
}

🔸 코드 해석 🔸

• 재귀메소드 dfs로 수를 선택해서 ArrayList에 저장한다.
  • ArrayList에 이미 포함되어 있는지 확인한다.
• ArrayList에 저장한 수가 m개가 되면 출력한다.

---

🔸 end 🔸

• 스택으로 구현해보려고 했지만, 너무 복잡해지는 것 같아 재귀 메소드로 구현했다.