[JAVA][BOJ][S3] 10974. 모든 순열

10974번: 모든 순열

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

풀이

순열을 이용해서 풀 수 있는 기본 문제다

자세한 코드는 아래 링크에 정리해 두었다

순열, 조합, 부분집합

 

코드

package 문제풀이;

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

public class S3_10974_모든순열 {
	static int N;
	static int[] input, numbers;
	static boolean[] isSelected;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		input = new int[N];
		numbers = new int[N];
		isSelected = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			input[i] = i+1;
		}
		
		P(0);
		
		System.out.println(sb);

	}

	private static void P(int cnt) {
		if(cnt == N) {
			for (int i = 0; i < N; i++) {
				sb.append(numbers[i] + " ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(isSelected[i]) continue;
			numbers[cnt] = input[i];
			isSelected[i] = true;
			P(cnt+1);
			isSelected[i] = false;
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘