백준 10972 - 다음 순열 [자바] [파이썬]

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

10972번: 다음 순열

---

풀이 과정

순열이 주어졌을 때, 사전순으로 다음에 오는 순열을 구하는 문제이다.

 

C++에서는 next_permutation 함수를 통해 다음 순열을 구할 수 있지만, 자바와 파이썬에서는 다음 순열을 구하는 내장 함수가 존재하지 않으므로 직접 다음 순열을 구하는 알고리즘을 구현해줘야 한다.

 

다음 순열을 구하는 알고리즘은 다음과 같은 4단계로 이루어진다.

1. a[i-1] < a[i]인 가장 큰 i를 찾는다.

2. a[i-1] < a[j]인 가장 큰 j를 찾는다.

3. a[i-1]과 a[j]를 교체한다

4. a[i]부터 끝까지 뒤집어준다

 

C++에서는 swap함수가 있고 파이썬은 한 줄로 스왑이 가능한데 함수를 따로 만들거나 보조 변수를 하나 두거나 해야 해서 코드가 좀 길어지는 감이 있는 것 같다.

---

소스 코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws 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());
		}
		
		int a = N-1, b = N-1;
		
		while (a > 0 && arr[a-1] > arr[a]) { // arr[i-1] < a[i]인 가장 큰 i를 탐색한다
			a--;
		}
		
		if (a == 0) {
			System.out.println(-1);
			return;
		}
		
		while (b > 0 && arr[a-1] > arr[b]) { // arr[i-1] < a[j]인 가장 큰 j를 탐색한다
			b--;
		}
		
// arr[i-1]과 a[j]의 값을 바꾼다
		int temp = arr[a-1];
		arr[a-1] = arr[b];
		arr[b] = temp;
		b = N-1;
		
// arr[i]부터 모든 순서를 뒤집는다
		while (a < b) {
			temp = arr[a];
			arr[a] = arr[b];
			arr[b] = temp;
			a++; b--;
		}
		
		
		
		for (int i = 0; i < N; i++) {
			sb.append(arr[i]).append(" ");
		}
		
		System.out.print(sb.toString());
	} // end of main
} // end of class

 

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
i = len(a) - 1

while i > 0 and a[i-1] >= a[i]:  # a[i-1] < a[i]인 가장 큰 i를 찾는다
    i -= 1

if i <= 0:
    print(-1)
    exit(0)

j = len(a) - 1

while a[i-1] >= a[j]:  # a[i-1] < a[j]인 가장 큰 j를 찾는다
    j -= 1

a[i-1], a[j] = a[j], a[i-1]  # a[i-1]과 a[j]를 교체한다
j = len(a) - 1

while i < j:  # a[i]부터 끝까지 순열을 뒤집는다
    a[i], a[j] = a[j], a[i]
    i += 1
    j -= 1

print(' '.join(map(str, a)))  # a를 출력한다