[Leetcode] 31. Next Permutation

문제 : https://leetcode.com/problems/next-permutation/

---

정수 배열이 있을 때 해당 배열의 요소들의 순서를 바꿔서 사전순 다음 시퀀스로 만들어라. 만일 불가능하다면 사전순 가장 작은 순서로 재배열해야한다.

예를 들어, arr = [2, 1, 3]이라면 사전순 다음 순서인 [2, 3, 1]로 재배열 시켜야한다.

---

전부 내림차순으로 정렬된 순열의 다음 사전순 배열은 이들을 역순한 것과 같다.

예를 들어, arr = [3, 2, 1]의 경우 다음 사전순 배열은 [1, 2, 3]이다.

내림차순된 배열의 다음 사전순 배열을 구하는 방법을 알았으니 내림차순 배열의 가장 앞에 있는 숫자를 해당 숫자보다 큰 수들보다 가장 작은 수로 바꾸면 다음 사전순 배열을 구할 수 있다. 

 

말이 좀 어려우니, arr = [1, 3, 5, 4, 2] 를 예로 들어보자. 뒤에서부터 내림차순 배열인 것을 구해보면 [5, 4, 2]이다.

이 배열의 앞에 있는 수는 3이다. 이제 3보다 큰 수들 중에 가장 작은 수를 구해야 한다.

문제에서 배열의 요소들의 순서를 바꿔서 구하라고 했기 때문에 배열에 존재하는 수들 중 하나로 대체되어야 한다. 

사전순 다음 순열을 구하기 위해서는 앞에 수는 웬만하면 바꾸면 안되고 뒤에서부터 수를 조정해야 한다. 따라서 뒤에 있는 내림차순 배열([5,4,2])을 앞에서부터 탐색하면서 조건에 만족하는 수를 구한다. 예시에서 이 수는 4가 된다. 이제 두 수를 바꿔준다. 두 수를 바꾸면 arr = [1, 4, 5, 3, 2] 가 된다. 수를 바꿔도 내림차수 배열은 여전히 정렬되어 있음을 확인할 수 있다. 이제 해당 내림차순 배열을 역순으로 바꿔주면 정답이 된다. [1, 4, 2, 3, 5]

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/31.%20Next%20Permutation.cpp

---

참고 : https://leetcode.com/problems/next-permutation/solution/