[코드트리/INTERMEDIATE LOW] n개 중에 m개 뽑기 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🧩  해결 아이디어

• 백트래킹 (조합)

- 마지막으로 뽑힌 숫자와 지금까지 뽑은 갯수를 값으로 가져가서 뽑을 수 있는 원소 후보들을 탐색한다.

- 시간 복잡도: O(M)

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] arr;
 
    static List<Integer> combList = new ArrayList<>();    // 조합 리스트
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        comb(1, 0);
        System.out.println(sb);
    }
 
    private static void comb(int lastNum, int depth) { // 마지막으로 뽑힌 숫자, 지금까지 뽑은 갯수 저장
        // M개 뽑았을 때, 출력
        if(depth == M) {
            print();
            return;
        }
 
        // 뽑을 수 있는 원소 후보들 탐색
        for(int i = lastNum ; i <= N ; i++) {
            combList.add(i);
            comb(i + 1, depth + 1);
            combList.remove(combList.size() - 1);
        }
    }
 
    // 조합 리스트 출력 메소드
    private static void print() {
        for(int i = 0 ; i < combList.size() ; i++) {
            sb.append(combList.get(i)).append(" ");
        }
        sb.append("\n");
    }
}

 

 

---

🔺 다른 풀이들

- 2^N 재귀 생성 : 현재 숫자를 뽑을지 말지 경우의 수 나눠 탐색

import java.util.Scanner;
import java.util.ArrayList;
 
public class Main {
    public static int n, m;
    public static ArrayList<Integer> combination = new ArrayList<>();
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        
        findCombination(1, 0);
    }
 
 
    // 지금까지 뽑은 갯수와 뽑을지 말지를 결정할 숫자를 인자로 받음
    public static void findCombination(int currNum, int cnt) {
        // n개의 숫자를 모두 탐색했으면, 탐색 중지
        if(currNum == n+1) {
            // 탐색 과정에서 숫자 m개 뽑은 경우 답 출력
            if(cnt == m)
                printCombination();
            return;
        }
 
        // case 1) idx에 해당하는 숫자 "사용했을 때" 탐색
        combination.add(currNum);
        findCombination(currNum + 1, cnt + 1);
        combination.remove(combination.size() - 1);
 
        // case 2) idx에 해당하는 숫자 "사용하지 않았을 때" 탐색
        findCombination(currNum + 1, cnt);
    }
 
    // 방문한 원소들 출력 메소드
    public static void printCombination() {
        for(int i = 0; i < combination.size(); i++)
            System.out.print(combination.get(i) + " ");
        System.out.println();
    }
}

 

---

💬 느낀 점

해당 번호 뽑거나 안 뽑거나 한 경우를 이렇게 나누는 거구나...!!!

여태 문제 풀면서 몰랐는데 이렇게 재귀를 이제서야 좀 온전히 파악하다....ㅠ

 

1회독	2회독	3회독	4회독	5회독
V	12.20

---

(참고)

✔ 코드트리