LeetCode : 47. Permutations II

전형적인 순열을 사용하는 문제이지만, 중요한 점은 중복된 숫자가 있는 것이다!

따라서, 중복되는 결과를 만들어내지 않기 위한 조치가 필요하다.

 

1. 순열을 만들어내고 마지막에 ans에 있는 벡터들을 탐색하며 같은 배열이 없는 지 확인

시간 매우 많이 소요....(당연한 것,,)

faster than 5.08%인가??ㅋㅋㅋ

 

class Solution {
public:
    int n;
    vector<int> v;
    int visited[10] = {0, };
    vector<vector<int>> ans;
    
    void permutation(int num, vector<int>& nums){
        if(num==n){
            bool check2 = true;
            for(int i=0; i<ans.size(); i++){
                bool check = true;
                for(int j=0; j<ans[i].size(); j++){
                    if(ans[i][j]!=v[j]){
                        check = false;
                        break;
                    }
                }
                if(check==true){
                    check2 = false;
                    break;
                }
            }
                
            if(check2==true){
                ans.push_back(v);
            }
            return;
        }
        
        
        for(int i=0; i<nums.size(); i++){
            if(visited[i]) continue;
            visited[i] = true;
            v.push_back(nums[i]);
            
            permutation(num+1, nums);
            visited[i] = false;
            v.pop_back();
        }
    }
 
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        n = nums.size();
        permutation(0, nums);
        
        return ans;
    }
};

 

2. next_permutation 사용

맨 처음 배열 자체를 sort해주고 next_permutation을 사용하면 중복되는 순열을 제거해서 만들어준다.

ex) [1, 1, 2] => [1, 1, 2], [2, 1, 1, ], [1, 2, 1] 로 만들어준다.

그리고 시간도 fater than 98.88%....amazing,,,

 

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        do{
            ans.push_back(nums);
        }while(next_permutation(nums.begin(), nums.end()));
        
        return ans;
    }
};