[백준] N과 M (5)

🔗 문제 보기 - [백준] N과 M (5)

📖 문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

✍ 입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

📄 출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.StringTokenizer;  
  
public class Main {  
    static int n, m;  
    static int[] arr;  
    static int[] result;  
    static boolean[] visited;  
    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());  
  
        arr = new int[n];  
        result = new int[n];  
        visited = new boolean[n];  
  
        st = new StringTokenizer(br.readLine());  
        for(int i = 0; i < n; i++) {  
            arr[i] = Integer.parseInt(st.nextToken());  
        }  
        
        Arrays.sort(arr);  
        recursion(0);  
  
        System.out.println(sb);  
    }  
  
    private static void recursion(int val) {  
        if(val ==  m) {  
            for(int i = 0; i < m; i++) {  
                sb.append(result[i]).append(" ");  
            }  
            sb.append("\n");  
            return;  
        }  
        
        for(int i = 0; i < n; i++) {  
            if(!visited[i]) {  
                visited[i] = true;  
                result[val] = arr[i];  
                recursion(val + 1);  
                visited[i] = false;  
            }  
        }  
    }  
}

🧩 코드풀이

1. 배열 arr에 값들을 입력 받고, Arrays.sort를 이용하여 배열을 오름차순으로 정렬해줍니다.
2. 이후 recursion 메소드를 호출하여 0번 인덱스부터 재귀를 시작합니다.
3. 우선 base case로 인자값이 val이 m과 값이 같으면 result 배열에 담아뒀던 값들을 StringBuilder에 추가하며 return 합니다.
4. 이외에는 반복문을 순환하며 방문한 값인지 체크하는 visited 배열로 체크하여 방문하지 않은 인덱스는 result 배열에 값을 추가하며 인자 값인 val을 +1 한 값으로 다시 호출 해줍니다.
5. 마지막으로 StringBuilder 내용을 출력해줍니다.