순열(perputation) 알고리즘 1, 다음 순열 찾기

                                    🔔 n: 1 ~ 100, should in place!!

🤔 입력이 작은데 O(n²)로 풀어보는건 어떨까?
❌ dictionary생성
>>> in place라서 s: O(1)으로 해야함

                                    🕹️ 게임처럼 생각해보자.

♟️ 각 자릿수는 승격을 원하는 캐릭터이다.
📜 승격 규칙
>>> 가장 큰 수보다 앞의 캐릭터가 승격을 시도한다.
    >>> 승격을 하려면 다음을 만족 해야 한다.
        >>>  <승격 조건 1> 가장 큰 수와 두 번째로 큰 수가 서로 붙어 있어야 한다.
        >>>  <승격 조건 2> 가장 큰 수 뒤에 아무런 숫자가 없어야 한다.

    >>> 승격 시 해당 자릿수는 선택 가능한 수에서 자신 다음으로 큰 수이다.

    >>> 승격 캐릭터 기준으로 뒷자리는 모두 오름차순으로 정렬된다.
    >>> [❌승격에 실패한 경우]
        >>> 내부 승격이 행해진다.

📜 내부 승격
>>> 내부 승격은 처음 배열에서 가장 큰 수 이후의 캐릭터들을 slicing하여 승격을 시도하는 시스템이다.
    >>> 내부 승격은 📜승격 규칙을 적용 받으며, 이때 가장 큰 수는 전체 배열에서 두번째로 큰 수이다.

                                    class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """

        N = len(nums)

        # set king
        king = -9999
        king_idx = -99
        for i,n in enumerate(nums):
            king = max(n, king)
            king_idx = i

        if king_idx == 0:

        else:
            selected = {}

            # set map
            for i in range(1, N + 1):
                selected[i] = 0

            # set selecetd
            for i in range(king_idx - 1):
                if i not in selected:
                    prinf(f"{i} is not in selected!!")
                    break

                selected[i] = 1

            # find prince
            prince = -9999
            prince_idx = -99
            for i in range(king_idx + 1, N):
                prince = max(prince, nums[i])
                prince_idx = i

            print(f"prince: {prince}, idx: {idx}")

            if prince_idx - king_idx == 1:
                # choose second = find next bigger one
                # set candidate value 1
                selected[king_idx - 1] = 1
                judged_idx = king_idx - 1
                judged = nums[judged_idx]

                nn = -999
                for key in selected:
                    nn = max(nn, key)

                # find idx for in - place
                nn_idx = -99
                for i, n in enumearte(nums):
                    if n == nn:
                        nn_idx = i

                if nn < 0:
                    print(f"can't find target_idx something is wrong ... ")
                    break

                nums[judged_idx] = nn
                nums[nn_idx] = judged

                ❌❌❌ 여기서 막혔다.

                                    📜 고대 인도의 수학자 나라야타 판티타가 최초로 제안한 것으로 알려져 있는 표준알고리즘의 일부이다.

✅ 오른쪽에서 왼쪽으로 탐색한다.

✅ 처음으로 값이 증가하지 않는 지점을 찾는다.
>>> 📌 해당 지점을 pivot으로 둔다

✅ 📌pivot이후(=suffix)를 탐색하여 가장 오른쪽에 위치한 pivot 다음으로 큰 값을 찾는다.

✅ 📌pivot과 해당 값을 swap

✅ swap 이후 suffix를 reverse한다.

                                    class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        N = len(nums)

        # find pivot
        pivot = 99999
        p_idx = 99
        for i in range(N - 1, 0, -1):
            print(i)
            if nums[i - 1] < nums[i]:
                pivot = nums[i - 1]
                p_idx = i - 1
                break

        if pivot == 99999:
            # [3, 2, 1] -> [1, 2, 3]
            nums.reverse()
        else:
            target = 99999
            t_idx = 999
            for i in range(p_idx + 1, N):
                if nums[i] > pivot:
                    target = min(target, nums[i])
                    t_idx = i

            # swap
            nums[p_idx] = target
            nums[t_idx] = pivot

            # reverse suffix
            suffix = nums[p_idx + 1:]
            suffix.reverse()

            # updated by reversed suffix
            prefix_len = N - len(suffix)
            for i in range(p_idx + 1, N):
                nums[i] = suffix[i - prefix_len]

                                    class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        N = len(nums)

        # find pivot
        i = N - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i < 0:
            nums.reverse()
            return

        # find swap target
        j = N - 1
        while nums[j] <= nums[i]:
            j -= 1

        # swap 📌
        nums[i], nums[j] = nums[j], nums[i]

        # reverse suffix 📌
        left, right = i + 1, N - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1