[JAVA] 백준 알고리즘 10974번 문제풀이 (모든 순열)

 

 

 

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

10974번: 모든 순열

 

 

● 모든 순열 (10974번)

​

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

 

 

 

 

 

 

import java.util.Scanner;
//10974번
public class Main {

	public static boolean permutation(int[] a) {
		int i = a.length - 1;
		while (i > 0 && a[i - 1] >= a[i]) {
			i -= 1;
		}
		if (i <= 0) {
			return false;
		}
		int j = a.length - 1;
		while (a[j] <= a[i - 1]) {
			j -= 1;
		}

		int temp = a[i - 1];
		a[i - 1] = a[j];
		a[j] = temp;

		j = a.length - 1;
		while (i < j) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i += 1;
			j -= 1;
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = i + 1;
		}
		do {
			for (int i = 0; i < n; i++) {
				System.out.print(a[i] + " ");
			}
			System.out.println();
		} while (permutation(a));
	}

}

↓ 소스풀이 ↓

​

우선, 메인에서 수를 입력받습니다.

입력받은 갯수만큼 배열을 생성해주고, for문을 사용해서 1부터 입력한 숫자만큼 1씩 증가해서 각배열에 저장해줍니다.

do-while문을통해서 permutation메소드의 리턴값이 불리언이기에 true일경우 for반복문을통해 값을 출력해줍니다.

이제 permutation메소드를 보면 매개변수로 배열a를 받습니다.

배열에 0인자부터 값을 넣었기때문에 수를 맞춰주기위해 -1을 해줍니다.

a[i-1]인자값이 a[i]보다 작은값을 찾기위해 while문을 돌려줍니다. 값을 찾았다면 다음 문장으로 넘어갑니다.

만약에 i가 0보다 작다면, false를 return합니다.

위에서 찾아준 값을 swap해줍니다.

그리고 마지막으로 값 저장해줍니다.

 

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

---