[코테]09-순열

다음 순열

임의의 수열을 다른 순서로 섞는 연산
크기가 N인 수열이 있을 때 순열의 개수는 N(N-1).....* 1

크기가 N인 수열의 서로 다른 순열은 총N!개가 있다.
모든 순열을 사전순으로 나열했을 때 A=[1,2,3]인 경우 사전순은 다음과 같다.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• 순서가 중요.
  1) 첫 순열
  2) 다음 순열
  .... 마지막 순열이 나올 때까지 반복.

첫 순열 : 오름차순, 비내림차순 정렬
마지막 순열 : 내림차순, 비오름차순 정렬

• 다음 순열(Next Permutation)

• A[1,2,3,4],,,,
  1) A[i-1]<A[i]를 만족하는 가장 큰 i를 찾는다.
  2) j>=i이면서 A[j]>A[i-1]를 만족하는 가장 큰 j를 찾는다.
  3) A[i-1]과 A[j]를 swap한다.
  4) A[i]부터 순열을 뒤집는다.

만약에 1 3 으로 시작하는 순열이 있다면
1 3 2 4
1 3 4 2 -> 13으로 시작하는 마지막 순열.
1 4 2 3 -> 14로 시작하는 첫 순열.

A = 7236541 -> 723으로 시작하는 마지막 순열.
N: 순열의 크기
1) i를 찾음 : O(N)
2) j를 찾음 : O(N)
3) i-1, j 교환 : O(1)
4) i~N 뒤집음 : O(N)
-> 다음 순열 시간복잡도 O(N)
-> 모든 순열 시간복잡도 O(N! * N)

함수(순열) <- 순열에 들어있는 값을 변경.
return 값 : true(다음 순열이 있음) or false(다음 순열이 없음)

• 다음 순열이 없다 : 마지막 순열.

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]= new int[n];
		for(int i=0; i<n; i++) {
			a[i]=sc.nextInt();
		}
		if(go(a)) {
			for(int i=0;i<n;i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
		}else {
			System.out.println("-1");
		}
	}
	
	public static boolean go(int a[]) {
		int i=a.length-1;
		while(i>0 && a[i-1] >= a[i]) {
			i--;
		}
		if(i<=0) return false;
		
		int j=a.length-1;
		while(a[j]<=a[i-1]) {
			j--;
		}
		
		int tmp=a[i-1];
		a[i-1]=a[j];
		a[j]=tmp;
		
		j=a.length-1;
		while(i<j) {
			tmp = a[i];
			a[i]=a[j];
			a[j]=tmp;
			i++;
			j--;
		}
		return true;
	}
}

이전 순열

• 부등호만 반대로 하면 이전 순열 구할 수 있음.

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]= new int[n];
		for(int i=0; i<n; i++) {
			a[i]=sc.nextInt();
		}
		if(go(a)) {
			for(int i=0;i<n;i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
		}else {
			System.out.println("-1");
		}
	}
	
	public static boolean go(int a[]) {
		int i=a.length-1;
		while(i>0 && a[i-1] <= a[i]) {
			i--;
		}
		if(i<=0) return false;
		
		int j=a.length-1;
		while(a[j]>=a[i-1]) {
			j--;
		}
		
		int tmp=a[i-1];
		a[i-1]=a[j];
		a[j]=tmp;
		
		j=a.length-1;
		while(i<j) {
			tmp = a[i];
			a[i]=a[j];
			a[j]=tmp;
			i++;
			j--;
		}
		return true;
	}
}

모든 순열

import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]= new int[n];
		for(int i=0; i<n; i++) {
			a[i]=i+1;
		}
		do {
			for(int i=0;i<n;i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
		}while(go(a));
	}
	
	public static boolean go(int a[]) {
		int i=a.length-1;
		while(i>0 && a[i-1] >= a[i]) {
			i--;
		}
		if(i<=0) return false;
		
		int j=a.length-1;
		while(a[j]<=a[i-1]) {
			j--;
		}
		
		int tmp=a[i-1];
		a[i-1]=a[j];
		a[j]=tmp;
		
		j=a.length-1;
		while(i<j) {
			tmp = a[i];
			a[i]=a[j];
			a[j]=tmp;
			i++;
			j--;
		}
		return true;
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.