[ETC] JAVA - NextPermutation 함수 - 공룡 루디

 NextPermutation 함수란?

NextPermutation은 말 그대로

다음 순열을 알아내는 함수입니다.

 

이때 다음 순열이란 사전 순으로 순열을 정렬했을 때 사전적으로 바로 다음번에 오는 순열이라는 뜻이죠

 

N개의 원소(원소 1~N)를 갖는 순열은 기본적으로 N! 개가 있습니다.

예를 들어 1,2,3의 순열은 사전 순으로

1,2,3

1,3,2

2,1,3 -이놈의 np?

2,3,1 -요놈

3,2,1

로 3! -> 6개 

 

만약 2,1,3 다음의 순열을 알고 싶다! 

이때 사용하는 게 nextPermutation입니다. 

2,1,3의 다음 순열은 2,3,1이죠

 

다른 말로 하면

A라는 순열의 다음 순열 B는

사전적으로 A 바로 다음에 오는 순열입니다.

 

그렇다면 마지막 순열인 3,2,1의 다음 순열은?

없습니다.

3,2,1보다 사전적으로 뒤에 오는 순열이 없기 때문이죠

 

그렇다면 어떻게 사전 순으로 바로 뒤에 오는 순열을 알 수 있을까요?

1,2,3,4라는 순열이 있을 때

사전적으로 다음에 오는 순열은 1,2,4,3으로 직감적으로 알 수 있죠

1,2,3,4->1,2,4,3 

이때 3과 4의 위치만 바뀌었지만,

 

N이 7일 때

6 1 7 5 4 3 2의 다음 순열은

6 2 1 3 4 5 7로 위치가 많이 바뀐 것을 알 수 있습니다.

 

눈으로는 쉽게 찾을 수 없죠...

 

---------------------------------------------------------------------------------------------------------------------------------

질문을 바꿔서

 

6 1 7 5 4 3 2라는 순열 보다 사전적으로 뒤에 오는 순열(바로 뒤가 아니어도 상관없음)을 만드는 방법은 무엇일까요?

 

7로 시작하는 모든 순열은 6 1 7 5 4 3 2 보다 사전적으로 뒤에 위치합니다.

ex) 7 1 6 5 4 3 2

     7 6 5 4 3 2 1 등

 

또한 6 2로 시작하는 모든 순열은 6 1 7 5 4 3 2 보다 사전적으로 뒤에 위치합니다.

 

또한 6 3으로 시작하는 모든 순열은 6 1 7 5 4 3 2 보다 사전적으로 뒤에 위치합니다.

등등

 

공통적인 사항은 순열 중 어떤 원소든 자기보다 뒤에 있는 원소 중

사전적으로 뒤에 위치한 원소랑 자리를 바꾸게 되면

해당 순열은 기존 순열보다 사전적으로 뒤에 위치하게 됩니다.

 

-------------------------------------------------------------------------------------------------

여기서부터는 기준과 타깃이라는 말을 쓰겠습니다.

2개의 원소를 교환한다고 했을 때

앞에 있는 애는 기준이고 뒤에 있는 애는 타깃입니다.

 

타깃의 조건은

기준보다 뒤에 있는 원소이며

동시에 사전적으로도 뒤에 위치한 원소이고

기준이 되려면 타깃을 적어도 1개 이상 가져야 합니다.

 

ex) 4 2 1 3에서

기준이 2일 때 1은 타깃이 될 수 없습니다.(사전적으로 앞서기 때문)

기준이 2일 때 3은 타깃이 될 수 있습니다.(기준보다 뒤에 위치, 사전적으로도 뒤)

기준이 2일 때 4는 타깃이 될 수 없습니다.(기준보다 앞에 위치한 원소기 때문)

4는 타깃이 될 수 있는 원소가 없어 기준이 될 수 없습니다.

 

 

예를 들어 1 3 2 4에서

1을 기준으로 하면 3,2,4는 모두 타깃이 될 수 있습니다.

따라서 기준과 어느 타깃을 바꿔도 만들어진 순열은 기존 순열보다 사전적으로 뒤에 위치하게 됩니다.

ex)

기존 순열 1 3 2 4

 

만들어진 순열

3 1 2 4

2 3 1 4

4 3 2 1

 

즉, 정리해서 말하자면 어떤 위치의 원소든(기준이 될 수 있는 원소) 자기보다 뒤에 위치한 원소들 중에서

사전적으로 뒤에 위치한 애(타깃)랑 교체만 하면

교체한 순열은 기존 순열보다 사전적으로 뒤에 위치한다.!

이게 가장 큰 포인트라고 생각합니다.

 

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

다시 6 1로 시작하는 순열 중 6 1 7 5 4 3 2 보다 사전적으로 뒤에 위치하는 원소가 있을까요?

정답은 위에서 말했기 때문에 없다는 것을 알 수 있습니다. (6 2 1 3 4 5 7) -> 6 2로 시작

 

왜냐하면 6 1 다음 7 5 4 3 2는 내림차순으로 정렬되어 있기 때문입니다. 

7은 자기보다 뒤에 위치한 모든 원소 5,4,3,2 보다 사전적으로 뒤에 위치합니다.

5는 자기보다 뒤에 위치한 모든 원소 4,3,2 보다 사전적으로 뒤에 위치합니다.

4는 자기보다 뒤에 위치한 모든 원소 3,2 보다 사전적으로 뒤에 위치합니다.

3은 자기보다 뒤에 위치한 모든 원소 2 보다 사전적으로 뒤에 위치합니다.

2는 뒤의 원소가 없습니다.

 

즉 7,5,4,3,2 원소들은 자기보다 뒤에 위치한 원소 중에서

자기보다 사전적으로 뒤에 위치한 원소를 찾을 수 없기 때문입니다.

 

바꿔 말하면 7,5,4,3,2는 기준이 될 수 없습니다.

 

따라서 6 1로 시작하는 모든 순열은 6 1 7 5 4 3 2 보다 사전적으로 뒤에 위치할 수 없습니다.

 

그렇다면 6과 1중 기준을 정하고

타깃을 정해 교환해야 합니다.

6을 기준으로 하고 7을 타깃으로 했을 때 교환한 순열은

7 1 6 5 4 3 2로 사전적으로 뒤에 위치한 순열이 됩니다.

 

하지만 바로 다음에 오는 순열은 아니죠...

 

그렇다면 1을 기준으로 하면

어떤 타깃과 바꿔도 6 1 7 5 4 3 2 보다 사전적으로 뒤에 오는 것을 알 수 있습니다.

(이때 7 5 4 3 2는 모두 타깃이 됩니다.)

 

(횡설 수설 하는 감이 있지만 이렇게 해보면 기억에 잘 남습니다 ㅎㅎ.. )

 

그렇다면 1을 어떤 타깃과 바꿀 것인가?

물론 아무 타깃과 바꿔도 기존 순열보다 사전적으로 뒤에 위치합니다.

(7,5,4,3,2 중 누구와 바꿔도 됩니다.)

 

6 7 1 5 4 3 2  (1과 7 교환했음)

6 5 7 1 4 3 2  (1과 5 교환했음)

6 4 7 5 1 3 2  (1과 4 교환했음)

6 3 7 5 4 1 2  (1과 3 교환했음)

6 2 7 5 4 3 1  (1과 2 교환했음)

 

그렇다면 어떤 타깃과 위치를 바꿔야지 가장 사전 순으로 앞설까요?

 

바로 6 2 7 5 4 3 1입니다.

2를 타깃으로 했을 때입니다.

 

--------------------------------------------

다시 6 1 7 5 4 3 2 바로 다음에 오는 순열을 구하고 싶은데

1과 2를 교환했더니 6 2 7 5 4 3 1로 

사전적으로 뒤에 오는 순열을 구했습니다.

하지만 바로 다음 순열은 아닙니다.

 

 

여기서!!

기준 원소의 위치로 오게 된 원소 2

뒤의 모든 원소를 오름 차순으로 정렬하면

6 2 7 5 4 3 1----> 6 2 1 3 4 5 7

6 2 1 3 4 5 7 이

6 1 7 5 4 3 2 바로 다음에 오는 순열이 됩니다.

 

------------------------------------------------------------------------------------

위의 순열 6 1 7 5 4 3 2에서

6과 1중 기준을 1을 선택한 이유는?

Why? 6을 기준으로 타깃과 교환하게 되면 7이랑 바꿔야 하는데 한참 뒤에 있는 순열이 됩니다.(7 1 6 5 4 3 2)

 

여기서 그럼 기준이 가능한 원소 중 가장 뒤에 있는 기준이 

선택되어야 한다는 것을 알 수 있습니다.

(영향력?을 가장 적게 끼쳐야지 다음 순열이 가까워집니다.)

 

만약 내가 친구한테 돈을 갚아야 하는데

친구가 24153원(원금)을 보여주고 네가 숫자 2개를 바꿔서 나한테 갚아!

하지만 갚는 돈은 24153보다 사전적으로 뒤에 와야 해(이자가 있어)!

이랬다고 생각해보죠

 

자... 돈이 별로 없어 친구에게 조금만 주고 싶다고 해봅시다.

 

여기서 기준은 2 ,4, 1 이 될 수 있습니다.(타깃이 있기 때문이죠)

만의 자리 수 2는 영향력이 너무 크죠 

(타깃이 4,5 가능) 

42153원 또는 54123원이 돼버리죠...

 

천의 자리 수 4는 타깃이 (5만 가능)

25143원 (많이 안 늘었네요)

 

백의 자리 수 1은 타깃이 (5와 3 가능)

24351원 (원금보다 크면서(사전적으로 뒤) 가장 가깝게 바뀌었네요)

 

기준을 1로 했을 때 가장 적게 돈을 갚을 수 있습니다.

기준들 중1의 영향력이 가장 적기 때문이죠(백의 자리)

(단순히 1이 가장 작아서가 아니라 만원(2), 천 원(4), 백 원(1) 가중치로 보았을 때 가장 작기 때문)

 

-----------------------------------------------------------------------------------------------------------

퀴즈

Q : 21453원 일 땐 기준이 될 수 있는 원소들은?

A : 2 1 4

 

Q : 그렇다면 가장 뒤에 있는 기준은?(가장 영향력이 적은 기준)?

A : 4

 

Q : 6 2로 시작하는 가장 사전적으로 앞서는 순열은?(N=7)

A :  6 2 1 3 4 5 7

어떻게 알 수 있나?

2 뒤의 원소들은 바로 오름 차순으로 정렬되어있기 때문입니다.

 

Q : 6 3 7로 시작하는 가장 사전적으로 앞서는 순열은?(N=7)

A : 6 3 7 1 2 4 5

마찬가지로 7 뒤의 원소들을 오름 차순으로 정렬했기 때문입니다.

 

--------------------------------------------------------------------------------------------------------------

정리

 

step 1. 기준을 정하자!

 

step 2. 기준은 가장 영향력이 적은 위치에 있는 원소로!

 

step 3.  2에서 가장 영향력이 적은 기준을 정했으면 기준 뒤는 자동으로 내림차순일 수밖에 없다.

( 기준 원소들이 내림차순 이어야지 해당 기준이 가장 영향력이 적은 기준임)

 

ex-1)

보라색-> 기준이 될 수 있는 원소

6 1 7 5 4 3 2 0

6과 1이 기준 될 수 있음

 

정한 기준이 가장 영향력이 적은 기준이 아닐 때

6의 뒤는 1 7 5 4 3 2 0(내림차순이 아님) ->X

 

정한 기준이 가장 영향력이 적은 기준일 때

1의 뒤는 7 5 4 3 2 0(내림차순임)->O(선택)

 

ex-2)

6 1 7 5 4 3 0 2

정한 기준이 가장 영향력이 적은 기준이 아닐 때 (1이 가장 영향력이 작은 기준이라고 잘못 고르면)

6 1 7 5 4 3 0 2 -> 1 뒤는 내림차순이 아님

 

다시 0이 가장 영향력 적은 기준으로 잘 골랐을 경우 6 1 7 5 4 3 0 2 -> 0 뒤는 내림차순

 

 

step 4.  제일 뒤의 타깃을 고른다.

(내림차순으로 정렬되어 있기 때문에 가장 뒤의 타깃이

다른 타깃들에 비해 사전적으로 앞에 오기 때문에 기존 순열과 거리가 가장 적게 벌어진다.)

 

step 5. 기준과 타깃을 교환한다. (기존 순열과 가까운 순열이 됨)

 

step 6. 원래 기준의 위치 뒤 모든 원소를 오름 차순으로 정렬한다.(다음 순열!)

 

------------------------------------------------------------------------------------------------------------------------

 

여기까지가 예시로 nextPermutation을 해본 겁니다.

 

위에서 말한 내용을 모두 코드로 바꾸면

nextPermutation을 구할 수 있습니다!!

 

어떻게 구현하냐에 따라서

효율이 좋을 수도 있고

효율이 안 좋을 수도 있습니다.

 

그렇다면 어떻게 효율적으로 짤 수 있을까?

 

바로

1. 뒤에서부터 기준을 찾고(타깃이 있는가? -> 뒤에 원소가 나보다 크면 내가 가장 뒤에 있는 기준!)

2. 뒤에서부터 타깃을 찾는다.

3. 기준과 타깃을 스왑 한다.

4. 원래 기준 뒤에 있던 원소 (위치로 따져야 함)를 내림차순으로 정렬한다.

5. 완성...

 

아래 코드는 백준 문제 풀이로 nextPermutation을 구현했습니다.

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

10972번: 다음 순열

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

public class NextPermutaion {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		

		int arr[] = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		if(nextPermutation(arr)) {
			for(int n:arr) {
				sb.append(n).append(" ");
			}
			
			System.out.println(sb.toString());
		}else {
			System.out.println(-1);
		}

	}


	// 다음  순열이 있으면 return true else return false;
	private static boolean nextPermutation(int[] p) {

		int N = p.length ;


		// step 1-1.가장 영향력이 적은 기준을 찾기위해서 뒤에서 부터 기준을 찾자
		// 맨 뒤는 기준이 어차피 될 수 없음
		// 따라서 N -1 부터가 아니라 N -2
		int originIdx = N-2;

		
		// step1-2.
		// 자기 보다 뒤에 수가 나보다 크면 기준이 될 수 있다.
		//뒤쪽부터 접근하면서 p[originIdx]보다 큰 p[originIdx+1]을 찾아야함
		while (originIdx >= 0 && p[originIdx] >= p[originIdx+1]) {
			--originIdx;
		}
		
		//맨 앞까지 왔는데 타겟이 없어 기준도 없다...
		//내림차순으로 순열이 정렬되어 있다는 의미--> 다음 순열은 없다.
		//기준인덱스가 -1 --> 기준이 없다. 즉 다음 순열도 없다.
		//만약 N==1 이면 originIdx는 처음부터 -1로 원소가 1개인 순열의 다음 순열은 당연히 없다.
		if(originIdx==-1) return false;
		
		
		//step2. 기준값과 교환할 targetIdx 찾기
		//타겟은 마지막 원소부터
		int targetIdx=N-1;
		
		
		// 코드가 여기까지 왔다는 의미 -> 기준이 있어 false가 리턴이 안됐다? -> 타겟은 무조건 있다.
		// p[originIdx]기준값 보다 p[targetIdx]이 크면 됨
		while(p[targetIdx]<=p[originIdx]) targetIdx--;
		
		
		// step 3,기준과 타겟을 교환
		swap(p,originIdx,targetIdx);
		
	
		//맨 뒤
		int k=N-1;
		
		// step 4, 원래 기준 index 뒤!! 부터 맨 뒤까지 오름차순 정렬
		int i=originIdx+1;
		
		//올바른 기준과 올바른 타겟을 교환 했다면 원래 기준 idx 뒤!!부터는 내림차순이 보장 됨 그래서 단순 스왑으로 오름차순으로 바꿀 수 있다.
		while(i<k) {
			swap(p, i++, k--);
		}
		
		return true;
	}
	
	static void swap(int[] arr, int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}

}

beforePermutation은 기준과 타깃을 구할 때 부등호 방향만 바꾸면 됩니다 :)

 

--------------------------------------------------마치며---------------------------------------------

 

엄청 어려운 알고리즘도 아니고

기존에 알았던 코드를 외워도 되지만

코드를 외우는 것보다 이해하고 구현하는 게 좋아서

나름의 방식대로 이해하고 정리하고 코드도 다시 작성했습니다.