<Medium> Next Permutation (LeetCode : C#)

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

📕 문제 설명

정수 배열이 주어질 때 순열 기준 다음으로 와야할 배열 반환하기 (이때 순열 기준 마지막 순서였다면 제일 첫 순서의 배열 반환)

replacement must be in place and use only constant extra memory

• Input
  정수 배열
• Output
  순열 기준 다음 정수 배열

예제

풀이

어떻게 순열의 다음 순서가 뽑히는지를 이해하면 쉽게 풀리는 문제

1. 뒤에서부터 값들 확인하며 처음으로 오름차순 위배되는 값의 index 찾기
2. 해당 index 뒤로 자신보다 작은 값 바로 앞의 값과 swap 후 reverse 시키기

public class Solution {
    public void NextPermutation(int[] nums) {
        int len = nums.Length;
        if (len <= 1) return;
            
        int i = len - 2;
        // 끝에서부터 처음으로 오름차순 아닌 값 index 찾기
        while (i >= 0 && nums[i] >= nums[i+1]) i--;
        if (i >= 0) // 해당 index 뒤로 자신 보다 큰 값 찾으면 swap 한 후 reverse
        {
            int l = len - 1;
            while (nums[i] >= nums[l]) l--;
            Swap(nums, i, l);
        }
        
        Reverse(nums, i+1, len-1); 
    }
    
    private void Reverse(int[] arr, int l, int r) 
    {
        while (l < r) Swap(arr, l++, r--);     
    }
    
    private void Swap(int[] arr, int i, int j) 
    {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

결과