백준 10973. 이전순열

🅰 백준 10973. 이전순열

10973번: 이전 순열

✏️ 문제 풀이

• 이전순열은 다음순열과 마찬가지로 np를 이용해서 풀었다.
• 하지만 내림차순으로 정렬되어야 하기 때문에 앞에서 부터 탐색을 하기 위해 np함수 내 데이터의 부등호만 변경해주었다.

✏️ 소스코드

package bruteforce;

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

public class Main_실버3_10973_손은성 {

	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());
		int numbers[] = new int [N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			numbers[i] = Integer.parseInt(st.nextToken());
		}
		
		if(np(numbers)) {
			for (int i = 0, end = numbers.length; i < end; i++) {
				sb.append(numbers[i]+" ");
			}
			System.out.println(sb);
		}else
			System.out.println("-1");
	}
	
	// prev_permutation 구하기(내림차순으로 순열 정렬)
	
	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;
	}

}

 

✅ 후기

•