코딩테스트를 위한 자바(java) 순열함수 구현 - 3

c, c++ 과 같은 다른 언어에서는 라이브러리로 순열함수를 지원하지만 자바에서는 순열함수 라이브러리를 지원하지 않아 직접 구현해야한다.

 

N개의 원소 중 M개를 뽑아 나열하는 모든 경우를 구하는 함수를 구현하는 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class P15654 {

	static int N, M;
	static ArrayList list = new ArrayList();
	static boolean[] visited;
	static int[] temp;
	static String result = "";

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();

		StringTokenizer st = new StringTokenizer(str, " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		str = br.readLine();
		st = new StringTokenizer(str, " ");

		for (int i = 0; N > i; ++i) {
			list.add(Integer.parseInt(st.nextToken()));
		}
        
        // 입력

		Collections.sort(list);
        
        // 정렬

		visited = new boolean[8];
		temp = new int[M];

		makePermutation(M, 0, temp, visited);
        
        // 순열함수

	}

	public static void makePermutation(int M, int current, int temp[], boolean visited[]) {
		if (current == M) {
			for (int i = 0; M > i; i++) {
				System.out.print(temp[i] + " ");
			}
			System.out.println("");
			return;
		}
		for (int i = 0; N > i; i++) {
			if (!visited[i]) {
				visited[i] = true;
				temp[current] = (int) list.get(i);
				makePermutation(M, current + 1, temp, visited);
				visited[i] = false;
			}
		}
	}
}

 

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

 

15654번: N과 M (5)