[백준] 10972 - 다음 순열 (자바/Java)

문제 링크

성능 요약

메모리: 15716 KB, 시간: 280 ms

분류

조합론(combinatorics), 수학(math)

문제 설명

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

---

다음 순열

바로 큰 다음 순열을 구하기

1 2 3 4

1 2 4 3

1 3 2 4

…

4 3 2 1

방법

1. 꼭대기(A): index = i, 오른쪽에서 출발, 가장 높은 곳
2. 낭떠러지(B): 꼭대기 왼쪽
3. 낭떠러지보다 큰 수(C): index = j,오른쪽에서 출발 → 오른쪽에서 출발, 최초로 발견된 낭떠러지보다 큰 수
4. B와 C를 교환(i-1, j)
5. 가장 오른쪽부터 꼭대기까지 순서를 뒤집음 (i부터 끝까지)\

package Silver.s3;

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

public class BOJ_10972_다음순열 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		nextPerm(arr);
	}

	static void nextPerm(int[] arr) {
		int a = -1; // 꼭대기
		int c = 0; // a-1보다 큰 수 찾기
		for (int i = 1; i < arr.length; i++) {
			if (arr[i - 1] < arr[i])
				a = i;
		}

		if (a == -1) {
			System.out.println(-1);
			return;
		}
		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] > arr[a - 1]) {
				c = i;
				break;
			}
		}
		// a-1과 c를 swap
		int tmp = arr[a - 1];
		arr[a - 1] = arr[c];
		arr[c] = tmp;
		// a부터 끝까지 거꾸로
		for (int i = 0; i < a; i++)
			System.out.print(arr[i] + " ");
		for (int i = arr.length - 1; i >= a; i--) {
			System.out.print(arr[i] + " ");
		}
	}

}

 

---

오름차순 정렬된 배열에서 시작해서 모든 다음 순열 찾기

package math;

import java.util.Arrays;

public class Math다음순열 {
	static int[] arr;

	public static void main(String[] args) {
		arr = new int[] { 1, 2, 3, 4 };

		do {
			System.out.println(Arrays.toString(arr));
		} while (np());
	}

	static boolean np() {
		int a = -1; // 꼭대기
		int c = 0; // a-1보다 큰 수 찾기
		for (int i = 1; i < arr.length; i++) {
			if (arr[i - 1] < arr[i])
				a = i;
		}
		if (a == -1) {
			return false;
		}

		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] > arr[a - 1]) {
				c = i;
				break;
			}
		}
		// a-1과 c를 swap
		int tmp = arr[a - 1];
		arr[a - 1] = arr[c];
		arr[c] = tmp;
		// a부터 끝까지 거꾸로
		Arrays.sort(arr, a, arr.length);
		return true;
	}

}