Next Permutation - LeetCode

Problem

1. input: 정수가 든 배열 nums
2. output: nums의 다음 조합 배열로 리턴
   • 1 <= nums.length <= 100
   • 0 <= nums[i] <= 100

Idea

다음 조합을 찾는 방법의 포인트는 2가지 이다.

1. 54321 의 다음은 12345 → 뒤에서부터 숫자를 볼때, 모두 오름차순이면 처음부터 끝까지 범위의 수를 reverse
2. 12354 의 다음은 12435 → 뒤에서부터 숫자를 볼때, 처음으로 오름차순이 아닌 수(3)의 idx = 2 (오름차순이었다는 말은 해당 구간은 최대값이므로 오름차순이 아닌 수를 다음 수로 바꿔야함) (ex. 132 다음 수는 213) → 2~끝의 숫자를 뒤에서부터 볼때, 처음으로 3 보다 큰 수 4 (처음으로 3 보다 큰 수를 찾았지만, 결국 이 수는 3 보다 1 큰 값) → 두 수를 스왑 ⇒ 12453 (앞자리 변경 354 → 453) → idx 2 이후의 수들 reverse ⇒ 12435 (앞자리 변경 후, 나머지 수는 최소의 값을 가져야 하므로)

Solution

1. 규칙..?

   • 뒤→앞에서 처음으로 오름차순이 아닌 수(인덱스) 찾기 → i
   • 뒤→i 에서 처음으로 nums[i]보다 큰 수(인덱스) 찾기 → j
   • nums[i] ↔ nums[j] 스왑
   • i 이후의 수 reverse

   class Solution {
       var nums = intArrayOf()
       
       fun nextPermutation(nums_: IntArray): Unit {
           nums = nums_
           var i = nums.size - 2
           // 배열의 끝에서부터 처음으로 이동하며 오름차순이 아닌 idx(i) 찾기
           while (i >= 0 && nums[i + 1] <= nums[i]) {
               i--
           }
           if (i >= 0) {
               var j = nums.size - 1
               // i 이후의 원소중 뒤에서 처음으로 i 보다 큰 값을 가진 idx(j) 찾기
               while (nums[j] <= nums[i]) {
                   j--
               }
               // i, j 스왑
               nums[i] = nums[j].also { nums[j] = nums[i] }
           }
           // i 이후 원소들 reverse
           reverse(i + 1)
       }
       
       // idx = start 이후 원소들 역순으로 뒤집기
       fun reverse(start: Int) { 
           var i = start
           var j = nums.size - 1;
           while (i < j) {
               nums[i] = nums[j].also { nums[j] = nums[i] }
               i++
               j--
           }
       }
   }
   

   시간 복잡도: 배열 순회 = n

   

Point

1. 규칙을 모르면 다소 힘든 문제 ⇒ 이번 기회에 외울 것