BOJ_10972_다음 순열

1

구분: 수학, 조합론
언어: Java
전략:

next permutation을 이용하는 문제이다 

 

NEXT PERMUTATION - 한 순열에서 사전 순으로 다음 순열 생성

1. 배열을 오름차순으로 정렬한 후 시작한다.

2. 맨 뒤부터 탐색하여 꼭대기(가장 큰 수, i번째)를 찾는다.

3. 꼭대기 바로 앞(i-1번째)보다 큰 수를 맨 뒤에서 부터 찾는다.(j)

4. i-1과 j를 교환한다.

5. 꼭대기 위치부터 맨 뒤까지 오름차순 정렬을 한다.

6. 2~5번 과정을 반복한다.

---

2. 코드

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		
		int[] arr = new int[n];
		for(int i = 0; i<n; i++) {
			arr[i] = scanner.nextInt();
		}
		
		if(np(arr)) {
			for(int i : arr) {
				System.out.print(i+" ");
			}
		}
		else {
			System.out.println(-1);
		}

	}//main
	
	private static boolean np(int[] arr) {
		int n = arr.length;
		
		int i = n-1;
		//꼭대기를 찾는다. - i는 꼭대기, i-1이 교환위치
		while(i>0 && arr[i-1]>arr[i])--i;
		
		//맨 마지막이면 
		if(i == 0)
			return false;
		
		int j = n-1;
		//맨 뒤에서부터 i-1보다 큰 거 찾는다 -> 변경할 것 
		while(arr[j]<arr[i-1])--j;
		
		swap(arr, j, i-1);
		
		int k = n-1;
		//꼭대기부터 끝까지 오름차순 정렬
		while(i<k) {
			swap(arr, i++, k--);
		}
		
		return true;
		
	}//np
	
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

}

 

---

3.

• next permutation을 연습할 수 있는 가장 기본 문제이다. 
• 처음에는 순열을 다 만들어 비교하는 방식으로 했으나 잘 문제가 풀리지 않았다.