[코드트리/INTERMEDIATE LOW] k개 중에 1개를 n번 뽑기 (JAVA)

🔺 문제

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int K, N;
    static int[] arr, result;
    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(), " ");
 
        K = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
 
        arr = new int[K];
        for(int i = 0 ; i < arr.length ; i++) {
            arr[i] = i + 1;
        }
        result = new int[N];
        
        back(0);
        System.out.println(sb.toString());
    }
 
    private static void back(int depth) {
        if(depth == N) {
            for(int i : result) sb.append(i + " ");
            sb.append("\n");
            return;
        }
 
        for(int i = 0 ; i < K ; i++) {
            result[depth] = arr[i];
            back(depth + 1);
        }
    }
}

 

 

 

🧩  해결 아이디어

• 백트래킹

. 재귀함수를 활용해 모든 순열과 조합을 만든다.

 

 

 

---

🔺 다른 풀이들

- 리스트를 활용해 숫자 뽑고 퇴각

import java.util.Scanner;
import java.util.ArrayList;
 
public class Main {
    public static int k, n;
    public static ArrayList<Integer> selectedNums = new ArrayList<>();
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        k = sc.nextInt();
        n = sc.nextInt();
        
        findPermutations(0);
    }
 
    // 중복 순열 구하는 메소드
    public static void findPermutations(int cnt) {
        if(cnt == n) {
            printPer();
            return;
        }
 
        // 1부터 k까지의 각 숫자가 뽑혔을 때의 경우 탐색
        for(int i = 1 ; i <= k; i++) {
            selectedNums.add(i);    // 숫자 뽑기
            findPermutations(cnt + 1);
            selectedNums.remove(selectedNums.size() - 1);    // 숫자 퇴각
        }
    }
 
    // 원소들 출력 메소드
    public static void printPer() {
        for(int i = 0; i < selectedNums.size(); i++)
            System.out.print(selectedNums.get(i) + " ");
        System.out.println();
    }
}

 

 

---

💬 느낀 점

백트래킹 너무 오랜만...

내 실력이 퇴각되었구나... 분발...

 

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

---

(참고)

[백준/JAVA] 15651번: N과 M (3)