[LeetCode#47] Permutation Ⅱ

 

❐ Description

---

[LeetCode#46] Permutation Ⅰ에 이은 문제이다.

이번 문제에서는 중복된 요소를 제어하는 것이 핵심이다.

 

 

 

 

 

❐ 탐색 과정에서 중복을 피하기

---

1. 아이디어

이번 문제를 효율적으로 풀이하기 위해서 꼭 떠올려야 하는 아이디어다.

동일한 숫자 중에서, 이전 숫자를 방문하지 않았다면 현재 숫자를 선택하지 않는다.

 

 

2. 그림으로 이해하기

만약 중복을 피하지 않는다면 아래와 같이 중복되는 경우도 탐색하게 된다.

 

하지만 탐색 과정에서 중복되는 경우는 탐색하지 않는다면 아래와 같이 불필요한 탐색을 건너 뛸수 있다.

 

 

3. 코드로 이해하기

private boolean hasDuplicatedElements(
        int i,
        int[] nums,
        boolean[] visited
) {
    return i > 0 && nums[i] == nums[i - 1] && !visited[i - 1];
}

 

i > 0

현재 확인 중인 요소가 배열의 첫 번째 요소가 아닌 경우에만 실행한다. 즉, 두 번째 요소 이상인

경우만 중복 검사를 진행한다. 왜냐면 배열의 첫 번째 요소(i == 0)는 이전 요소가 없으므로 중복

검사 대상에서 제외되기 때문이다.

 

nums[i] == nums[i-1]

현재 요소(nums[i])와 바로 앞의 요소(nums[i - 1])가 같은 경우를 찾는다.

순열을 생성할 때, 동일한 값이 중복되면 불필요한 중복 순열이 생성될 수 있기 때문에 이를 방지하기

위해 같은 값을 가지는 경우를 확인한다.

 

!visited[i-1]

바로 이전 요소(nums[i - 1])가 아직 방문되지 않은 경우에만 현재 요소를 제외한다.

중복된 요소(nums[i] == nums[i - 1])라 하더라도, 이전 요소(nums[i - 1])가 방문된 상태라면

순열에 포함된 것이므로 문제가 없다. 그러나 이전 요소가 방문되지 않았다면 중복된 값을 순열에

다시 포함하지 않도록 방지해야 한다.

 

 

 

 

 

❐ Solution

---

1. 탐색 후 중복 처리

public Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> elements = Arrays.stream(nums).boxed().toList();
        List<Integer> bucket = new ArrayList<>();
        Set<List<Integer>> results = new HashSet<>();
        permutationOperator(bucket, elements, results);
        return results.stream().toList();
    }

    private void permutationOperator(
            List<Integer> bucket,
            List<Integer> elements,
            Set<List<Integer>> results
    ) {
        if (elements.isEmpty()) {
            results.add(new ArrayList<>(bucket));
        }
        for (Integer e : elements) {
            List<Integer> copied = new ArrayList<>(elements);
            copied.remove(e);

            bucket.add(e);
            permutationOperator(bucket, copied, results);
            bucket.removeLast();
        }
    }
}

해당 풀이는 탐색 과정에서는 중복을 허용하고, 마지막에 Set을 이용해서 중복된 값을 걸러준다.

 

 

2. 탐색 과정에서 중복 처리

public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> bucket = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);

        permutationOperator(nums, visited, bucket, results);
        return results;
    }

    public void permutationOperator(
            int[] nums,
            boolean[] visited,
            List<Integer> bucket,
            List<List<Integer>> results
    ) {
        if (bucket.size() == nums.length) {
            results.add(new ArrayList<>(bucket));
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }

            // 중복 방지
            if (hasDuplicatedElements(i, nums, visited)) {
                continue;
            }

            visited[i] = true;
            bucket.add(nums[i]);
            permutationOperator(nums, visited, bucket, results);

            visited[i] = false;
            bucket.removeLast();
        }
    }

    private boolean hasDuplicatedElements(
            int i,
            int[] nums,
            boolean[] visited
    ) {
        return i > 0 && nums[i] == nums[i - 1] && !visited[i - 1];
    }
}

 

 

 

 

 

---