[백준/자바] 15654번: N과 M (5)

문제

https://www.acmicpc.net/problem/15654

풀이

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

순열을 구하는 문제

15649번: N과 M (1)은 1부터 N까지의 자연수의 순열을 구했지만, 이 문제는 입력 받은 수의 순열을 구하는 문제입니다.

    	st = new StringTokenizer(br.readLine());
    	nums = new int[n];
    	for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
    	Arrays.sort(nums);

• 오름차순으로 출력해 주어야 하기 때문에, 입력 받을 때 오름차순으로 정렬했습니다.

	private static void dfs(int idx) {
		if (idx == m) { // M개를 골랐다면 출력
			for (int i : li) sb.append(i).append(" ");
			sb.append("\n");
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if (!visited[i]) { // 배열에 넣은 값이 아니라면
				visited[i] = true; // 방문 처리 후
				li[idx] = nums[i]; // 값 삽입
				dfs(idx + 1); // 다음 인덱스 재귀
				visited[i] = false; // 백트래킹
			}
		}
	}

• 중복되는 수가 들어오면 안 되므로 visited 배열을 선언했습니다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static int[] li, nums;
	static boolean[] visited;
	
	private static void dfs(int idx) {
		if (idx == m) {
			for (int i : li) sb.append(i).append(" ");
			sb.append("\n");
			return;
		}
		
		for (int i = 0; i < n; i++) {
			if (!visited[i]) {
				visited[i] = true;
				li[idx] = nums[i];
				dfs(idx + 1);
				visited[i] = false;
			}
		}
	}
	
    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());
    	
    	st = new StringTokenizer(br.readLine());
    	nums = new int[n];
    	for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());
    	Arrays.sort(nums);
    	
    	li = new int[m];
    	visited = new boolean[n];
    	
    	dfs(0);
    	System.out.println(sb.toString());
    }
}