[알고리즘] LeetCode - Next Permutation

Description

• Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
• If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
• The replacement must be in-place and use only constant extra memory.

• Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
  1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

번역

• 입력으로 주어진 배열의 조합의 사전적 순서(lexicographic)에 따른 다음 조합을 리턴하라.
• 만약 다음 조합이 없다면, 가장 낮은 순서의 조합을 반환하라.(오름차순)
• 다음 조합을 만드는 작업은 in-place하게 진행되어야 하며 상수 공간 복잡도를 가져야 함
• 입출력에 대한 예시

  1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

도전!

한글로 번역한게 뭔가 더 어렵긴 한데 사전 순서로 조합을 만들 때 주어진 조합의 다음 순서에 해당하는 조합을 리턴하라는 의미이다.

보자마자 도저히 감이 안와서 한참 고민하다 패턴을 발견했는데 아래와 같다.

1. 배열의 마지막에서 부터 s[i] > s[i - 1]인 i를 찾는다.(인접한 두 요소가 오름차순으로 정렬된 경우)
2. i가 0보다 큰 경우 배열의 끝에서 부터 s[i] 보다 큰 s[j]를 찾아 i와 j를 swap해준다.
3. 이 후 i + 1 부터 마지막 까지의 요소는 오름차순으로 정렬되어야 한다.
4. 이 때 i + 1 이후의 요소들은 모두 내림차순으로 정렬되어 있으므로 뒤집어 주기만 하면 끝.

구현 코드

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  if (nums.length === 1) return;
  let i = nums.length - 2;
  let j = nums.length - 1;

  while (nums[i] >= nums[i + 1]) {
  	i--;
  }
    
  if (i >= 0) {
    while (nums[i] >= nums[j]) {
      j--;
    }
    swap(nums, i, j);
  }

  let k = i + 1;
  let l = nums.length - 1;
  while (k < l) {
	swap(nums, k, l);
	k++;
	l--;
  }
};

function swap(A, i, j) {
  const temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}