다음 순열

서론

​

❔ 문제

​
Leetcode 31, Next Permutation 문제이다. 아래는 leetcode의 링크이다.
https://leetcode.com/problems/next-permutation/

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

🤔고민

​
이 문제를 요약하자면, 사전식으로 모든 순열을 나열했을 때, 다음 순열을 구하는 것이 목표이다. 문제를 보고 가장 먼저 생각났던 방식은, 순열을 사전식으로 구하는 동시에 목표로 하는 다음 순열을 구하는 방법이다. time limit에 걸릴 것 같았지만 일단은 코드로 작성해보았다. 아무래도 재귀호출을 이용해서 구해나가는 방식이어서 모든 순열을 구하기에는 시간이 오래 걸렸다. 실제로 leetcode에 제출을 하니 time limit exceed 라며 시간초과 되었다.

그래서 다음 방식을 생각해보았다. 다음 순열을 찾기 위해서 뒤에서 부터 원소를 하나씩 탐색할 때, 현재 탐색하고 있는 원소가 다음 숫자로 바뀌면 지나온 다른 원소들은 정렬이 되는 규칙을 찾아냈다. 이를 이용하여 코드를 작성하였다.

코드

​
내가 작성한 코드는 아래와 같다.
​

class Solution{
public:
    void nextPermutation(vector<int>& nums){
        bool flag = false;
        //사전식로 순열을 배열했을 때 마지막 순열인지를 기록하기 위한 flag이다.

        for(int i = nums.size()-2; i>=0; i--){
            sort(nums.begin()+i+1,nums.end());
            //탐색하는 원소의 다음 원소 부터 끝까지 정렬을 수행한다.

            for(int k = i+1; k<nums.size(); k++){
            //탐색하는 원소보다 큰 원소 중 가장 작은 원소를 구하기 위한 for문이다.

                if(nums[k]>nums[i]){
                //찾았다면 swap을 수행한다.

                    flag = true;
                    swap(nums[k],nums[i]);
                    break;
                }
            }
            if(flag) break;
            //다음 순열을 찾았으므로 탐색을 종료한다.
        }
        if(!flag) sort(nums.begin(), nums.end());
        //위에서 swap이 이루어지지 않았으면 사전식 순열 배열에서 마지막 원소이므로 전체적으로 sort를 수행해준다.
    }
};

이렇게 코드를 작성하면 accepted 가 뜬다. 하지만 sort를 계속해서 사용하므로 그래도 시간이 늦게 걸리는 감이 있다.

아래는 leetcode discuss의 다른 사람의 해답이다. 내 코드보다 훨씬 효율적이다. 참고하는게 좋겠다.
https://leetcode.com/problems/next-permutation/discuss/1741631/100-FASTER-C%2B%2B-SOLUTION-O(1)-SPACE-O(N)-TIME