[Java] BOJ10974, 백준 - 모든 순열

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

10974번: 모든 순열

문제

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

 

입력

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

 

출력

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

 

<풀이>

해당 숫자로 만들 수 있는 모든 순열을 사전순으로 정렬해야 하기 때문에, 일일이 정렬해주며 다음 순열을 찾아주어서 모든 순열을 찾아보도록 하였다.

초기 수열은 arr배열에 넣어주었다.

다음 순열 찾는 방법

1. 현재 순열에서 순서가 잘못된 부분(i>j일 때, i번째 수가 j번째 수보다 큰 부분)을 순열의 맨 마지막 자리부터 찾는다.
2. 그런 부분이 없다면 false를 return(정렬이 완료된 상태), 있다면 true를 return
3. 다음 순열을 만들기 위해 바꿔야 할 두 수를 swap해준다.
4. a[i]부터 순열을 뒤집어준다.(왜냐면 중간에 바꿨으면 그 다음부터는 다시 처음부터 순열을 만들어서 찾아줘야 올바르게 다음 순열의 순서를 구할 수 있기 때문이다.)
5. 그렇게 return false일때까지 반복하면 모든 다음순열(=모든순열)을 구할 수 있게 된다.

소스 코드

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

public class Main {
	private static StringBuilder sb = new StringBuilder();
	private static int[] arr;
	private static int n;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		arr = new int[n];

		for (int i = 0; i < n; i++) {
			arr[i] = i + 1;
		}

		do {
			print(arr);
		} while (next_permutation());
		System.out.println(sb);

	}

	private static boolean next_permutation() {
		int i = n - 1;
		while (i > 0 && arr[i] < arr[i - 1])
			i--;

		if (i <= 0)
			return false;

		int j = n - 1;
		while (arr[j] < arr[i - 1])
			j--;

		swap(i - 1, j);
		j = n - 1;

		while (i < j) {
			swap(i, j);
			i++;
			j--;
		}
		return true;
	}

	private static void swap(int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	private static void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			sb.append(arr[i] + " ");
		}
		sb.append("\n");
	}

}

 

사실 직접 생각한건 아니고 이것저것 참고해서 풀은거라 내용 정리가 잘 안된다..

파이썬이나 C++의 경우 라이브러리가 있다지만 주 언어인 Java에는 없으니, 필요할 때 바로바로 짜서 쓸 수 있도록 몇 번 연습을 해봐야겠다.