[LeetCode] 47. Permutations II - 깊이우선탐색(DFS) + 해시셋(HashSet) + 비트마스크(BitMask) JAVA

https://leetcode.com/problems/permutations-ii/description/

코드설명

깊이우선탐색(DFS) + 해시셋(HashSet) + 비트마스크(BitMask)을 활용합니다.

 

처음에는 중복제거를 위해 HashSet을 사용했습니다.

 

하지만, 더 좋은 방법이 존재합니다. 이 코드를 활용합니다.

// i가 1이상부터,
// 1 1 1 2 정렬된 상황에서 이전숫자가 현재숫자랑 같을떄
// 이전숫자를 아직 방문한 적 없다면 continue (이미 방문한상태라면, 중복임. )
// 이유는 앞으로 다시 돌아가는경우이기 떄문.
    if(i > 0 && nums[i] == nums[i-1] && (visited & (1 << (i - 1) )) == 0) continue;

 

 

만약 [1, 1, 2] 가 존재한다고 합시다. 만약 중복제거를 안한다면?

(1, 1, 2)

(1, 2, 1)

(1, 1, 2)

(1, 2, 1)

(2, 1, 1)

(2, 1, 1)

 

이렇게 3! 로 총 6가지가 나옵니다. 역시나 중복개수가 존재합니다.

처음에 저는 항상 Arrays.sort로 순서를 정렬합니다.

이떄, 이를 활용하여 항상 1 1 1 2 와 같이 정렬되어, 하나의 숫자가 반드시 연속적으로 등장함을 알 수 있습니다.

이를 활용하여, 만약 서로 연속된 숫자인데 ->즉,  (1 1 1) 인데, 2번째 Index를 먼저 거쳤는데, num[2] == num[1] 은 서로 같으므로, 반대로 돌아가는경우 반드시 중복된 경우가 생김을 알 수 있습니다. 해당 로직을 활용하여 해결합니다. (완전히 이해가 가지는 않습니다만, 예제로 보면 이해가 갑니다.) 이를 통해 중복된 값은 첫번쨰 로 탐색한 경우에만 탐색하도록 할 수 있습니다.

코드

HashSet없이 중복코드 제거한 정답코드1입니다.

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        DFS(nums, 0, 1 << (nums.length), new HashSet<>(), new int[nums.length]);
        return answer;
    }
    
    void DFS(int[] nums, int level, int visited, HashSet<String> hashset, int[] perm){
        if(level == nums.length){
            ArrayList<Integer> temp = new ArrayList<>();
            for(int v : perm){
                temp.add(v);
            }
            answer.add(temp);
            return ;
        }

        for(int i=0; i<nums.length; i++){
            if( (visited & (1 << i)) == 0){
            // i가 1이상부터,
            // 1 1 1 2 정렬된 상황에서 이전숫자가 현재숫자랑 같을떄
            // 이전숫자를 아직 방문한 적 없다면 continue (이미 방문한상태라면, 중복임. )
            // 이유는 앞으로 다시 돌아가는경우이기 떄문.
                if(i > 0 && nums[i] == nums[i-1] && (visited & (1 << (i - 1) )) == 0) continue;

                visited |= (1 << i);
                perm[level] = nums[i];
                DFS(nums, level + 1, visited, hashset, perm);
                visited &= ~(1 << i);
            }
        }
    }
}

 

HashSet을 사용하여 중복Permutation을 제거한 정답코드2입니다.

class Solution {
    List<List<Integer>> answer = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        DFS(nums, 0, 1 << (nums.length), new HashSet<>(), new int[nums.length]);
        return answer;
    }
    
    void DFS(int[] nums, int level, int visited, HashSet<String> hashset, int[] perm){
        if(level == nums.length){
            StringBuilder sb = new StringBuilder();
            for(int v: perm) {
                sb.append(v);
            }
            if(hashset.contains(sb.toString()) == false){
                ArrayList<Integer> temp = new ArrayList<>();
                for(int v : perm){
                    temp.add(v);
                }
                answer.add(temp);
            }
            hashset.add(sb.toString());
            return ;
        }

        for(int i=0; i<nums.length; i++){
            if( (visited & (1 << i)) == 0){
                visited |= (1 << i);
                perm[level] = nums[i];
                DFS(nums, level + 1, visited, hashset, perm);
                visited &= ~(1 << i);
            }
        }
    }
}