[Misc][Medium] 31. Next Permutation

 

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

 

Q. 주어진 정수 배열 nums에서 다음 permutation 값을 찾아라. 

 

Solution

 이런 문제를 보면 아직도 정말 배워야 할 것이 넘침을 느낀다. 

 직관으로 풀기는 힘든 문제. 

 

 관련 알고리즘을 찾아본다. 

 

 우선 nums[i] < nums[i+1] 인 피봇 포인트를 뒤에서부터 검색해서 찾는다.

 이 피봇 포인트를 기준으로 뒤편의  값 중 피봇 포인트보다 큰 수장 가장 작은 값을 찾는다. 

 이 값과 피봇 포인트 값을 교체한다. 

 그리고 피봇 포인트 우측편 값들을 오름차순 정렬한다. 

 ( Reference : https://yoongrammer.tistory.com/109 )

 

 이것이 원하는 답이 된다. 

 

 로직대로 코드를 만들어 본다. 

 

public void NextPermutation(int[] nums) 
{
    // 1. Search for Pivot where nums[i]<nums[i+1].
    // 2. Swap values with pivot and the number that is the smallest one among bigger than the pivot.
    // 3. Descent-Sort right side of pivot.
    //
    
    // 피봇 포인트 검색.
    int idxPivot = -1;
    for(int q = nums.Length-2; q >= 0; --q)
    {
        if(nums[q] < nums[q+1])
        {
            idxPivot = q;
            break;
        }
    }
    if(idxPivot < 0)
    {
        Array.Reverse(nums);
        return;
    }

    // 피봇값보다 큰 값중 가장 작은 값 검색.
    int minAmongLagerThanPivot = int.MaxValue;
    int idxTarget = -1;
    for(int q = idxPivot+1; q < nums.Length; ++q) 
    {
        if(nums[q]>nums[idxPivot]) 
        {
            if(minAmongLagerThanPivot > nums[q])
            {
                minAmongLagerThanPivot = nums[q];
                idxTarget = q;
            }
        }
    }
    if(idxTarget < 0)
    {
        Array.Reverse(nums);
        return;
    }

    // 피봇값과 해당 값 교환.
    int temp = nums[idxTarget];
    nums[idxTarget] = nums[idxPivot];
    nums[idxPivot] = temp;

    // 우측편에 대해 오름차순 정렬.
    Array.Sort(nums, idxPivot+1, nums.Length-idxPivot-1);
}

 

 

 

적절한 결과를 얻었다.