LeetCode: 47번 (Permutations II) [JAVA]

문제 링크

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

Permutations II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 순열 순서 저장용 arr 생성 (모든 원소 -1로 초기화), 순열 집합 저장용 HashSet 생성
2. 순열 생성 함수 생성
   1) 파라미터 - nums 배열, nums 배열에 대한 인덱스(index), arr 배열
   2) index가 nums 배열 길이가 되면 순열 생성이 완료된 것으로, 우선 해당 순열을 나타내는 일종의 문자열 key를 생성해 HashSet에 값이 존재하는 지 확인 후, 없다면 해당 순열을 답에 저장 후 해당 key 또한 HashSet에 추가
   3) for문을 통해 전체 arr 배열을 돌며 원소가 -1인 곳이 생기면 해당 곳에 index를 삽입 후 다음 함수 호출
   4) 이후 해당 위치를 다시 -1로 초기화(백트래킹)
3. 결과 List<List<Integer>> 반환

 이전에 풀었던 문제인 46. Permutations의 응용 버전이다. 이전 문제에 비해 주어지는 배열 속 숫자들이 중복 가능하고, 결과 순열에서 순서가 중복되는 경우 해당 중복을 제거해야 하는 과정이 추가되었다. 그렇기 때문에 이전의 풀이에 순열의 집합을 하나의 문자열로 나타내어, 이를 Set으로 관리해 중복을 체크하는 과정을 추가했다.
 순열 생성 부분은 앞선 46. Permutations 문제와 동일하지만, 다만 순열 생성 완료 후에 주어진 arr을 돌며 현재 순열의 집합을 나타내는 문자열 key를 만든다. 그 다음 HashSet에 해당 값의 여부를 조사해, 만약 값이 없다면 기존에 없는 순서의 순열이므로 이를 결과 List에 추가하고 HashSet에 해당 key를 추가하면 된다.

 

class Solution {
    List<List<Integer>> result = new ArrayList<>();//리턴용 답안 배열
    HashSet<String> permutationString = new HashSet<>();//순열 집합 저장용 set

    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] arr = new int[nums.length];
        Arrays.fill(arr, -1);
        permutation(nums, 0, arr);
        return result;
    }

    void permutation(int[] nums, int index, int[] arr) {//순열 생성
        if (index == nums.length) {//nums 배열 모두 사용했으면
            StringBuilder key = new StringBuilder();

            for (int i = 0; i < arr.length; i++) {//해당 순열에 대한 문자열 key 생성
                key.append(nums[arr[i]]);
                key.append('.');
            }

            if (!permutationString.contains(key.toString())) {//기존에 없는 순열이라면 답에 추가
                List<Integer> set = new ArrayList<>();
                for (int i = 0; i < arr.length; i++) {//해당 순열 List 생성
                    set.add(nums[arr[i]]);
                }
                result.add(set);//답에 추가
                permutationString.add(key.toString());
            }

            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {//배열의 빈 곳이면
                arr[i] = index;
                permutation(nums, index + 1, arr);
                arr[i] = -1;//백트래킹을 위해 다시 빈 곳으로 표시
            }
        }
    }
}

결과