https://www.acmicpc.net/problem/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해줍니다.
그리고 마지막으로 값 저장해줍니다.
< 백준알고리즘 강의를 보고 참고하였습니다! >
'Dev. Etc > Algorithm' 카테고리의 다른 글
[JAVA] 백준 알고리즘 7576번 문제풀이 (토마토) (0) | 2019.11.09 |
---|---|
[JAVA] 백준 알고리즘 15649번 문제풀이 (N과M) (0) | 2019.11.08 |
[JAVA] 백준 알고리즘 2750번 문제풀이 (수 정렬하기) (0) | 2019.11.07 |
[JAVA] 백준 알고리즘 1182번 문제풀이 (부분집합의 합) (0) | 2019.11.06 |
[JAVA] 백준 알고리즘 1978번 문제풀이 (소수 찾기) (0) | 2019.11.04 |
[JAVA] 백준 알고리즘 1929번 문제풀이 (소수 구하기) (0) | 2019.11.03 |
[JAVA] 백준 알고리즘 2609번 문제풀이 (최대공약수와 최소공배수) (0) | 2019.11.02 |
[JAVA] 백준 알고리즘 1934번 문제풀이 (최소 공배수) (0) | 2019.11.01 |