백준 10972. 다음 순열

🅰 백준 10972. 다음 순열

10972번: 다음 순열

✏️ 문제 풀이

• 자바에는 없는 next-permutation을 구현하는 문제이다.
• 먼저 입력 배열을 오름차순으로 정렬하는 것이 중요하다. 정렬 후 np함수를 통해 데이터를 출력한다.
• np에 대한 내용은 따로 정리해서 올리겠다.

✏️ 소스코드

package bruteforce;

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

public class Main_실버3_10972_손은성 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int numbers[] = new int[N];
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		
		if(np(numbers)) {
			for (int i = 0; i < N; i++) {
				sb.append(numbers[i]+" ");
			}System.out.println(sb);
		}
		else System.out.println("-1");
	}
	private static boolean np(int numbers[]) {
		int N = numbers.length-1;
		
		int i = N;
		while(i>0 && numbers[i-1]>=numbers[i]) --i;
		if(i == 0)
			return false;
		
		int j = N;
		while(numbers[i-1]>=numbers[j]) --j;
		swap(numbers,i-1,j);
		
		int k = N;
		while(i<k) swap(numbers,i++,k--);
		return true;
	}
	
	private static void swap(int numbers[], int i, int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
}

 

✅ 후기

• 배웠던 내용이였는데 직접 구현하려니 어려웠다. 하지만 문제를 많이 풀어보니 손에 익어서 순열을 풀 때에 적극 활용 하고있다. 하지만 조합은 오름차순으로 안나오던데,, 이 문제는 더 찾아봐야겠다