LeetCode: 90번 (Subsets II) [JAVA]

문제 링크

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

Subsets II - LeetCode

풀이

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

1. 결과를 담을 List<List<Integer>> 리스트 생성 후, 초기 공집합 List 추가
2. 주어진 nums 배열을 돌며, 특정 숫자 - 숫자 등장 횟수를 쌍으로 HashMap 형태로 저장
3. 이후 결과 HashMap을 돌며, 다음을 반복
   1) 해당 숫자의 등장 횟수를 카운트
   2) 현재 까지의 List<List<Integer>> 리스트 속 부분집합 개수를 파악
   3) for문을 통해 기존 부분 집합 하나를 가져와, 현재 숫자를 1~등장 횟수까지 추가한 리스트들을 만들어 결과에 다시 추가
4. 결과 List<List<Integer>> 반환

 기존에 있는 숫자들의 집합에서 생성된 부분집합 리스트에서, 새로운 요소가 추가된 이후 전체 부분집합들을 계산하려면 기존 부분집합 리스트에 새로운 요소를 추가한 리스트들을 이어붙이면 된다. 다만 이 문제에선 특정 숫자가 중복 등장이 가능하기 때문에, 여러번 등장하는 숫자로 인해 발생할 수 있는 중복을 제거해주어야 한다.
 우선 정답을 저장할 List<List<Integer>> 리스트를 초기화한 다음, 공집합에 대한 부분집합 리스트를 하나 추가해준다. 그 다음에는 주어진 nums 배열을 한 번 돌면서, (특정 숫자, 숫자 등장 횟수) 형태로 HashMap을 통해 저장해준다. 이후 데이터를 저장한 HashMap을 돌면서, 기존의 부분집합들로부터 새로운 부분집합을 만들어 추가시켜주면 된다. HashMap을 돌면서 특정 숫자에 대해, 등장 횟수를 저장하고 현재까지의 부분집합 리스트를 파악한다. 그 다음에는 각 부분집합을 복사해온다음, 현재 숫자를 1개부터 등장횟수까지 추가하여 새로운 부분집합 리스트들을 만든 다음 다시 결과 List<List<Integer>> 리스트에 추가해면 된다. 이후 해당 탐색이 완료되면 결과 List<List<Integer>> 리스트를 반환해주면 된다.

 

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());

        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int num : nums) {//전체 nums를 돌며 숫자와 숫자의 개수를 count
            if (hashMap.containsKey(num)) {
                hashMap.replace(num, hashMap.get(num) + 1);
            } else {
                hashMap.put(num, 1);
            }
        }

        for (Integer num : hashMap.keySet()) {//전체 숫자 종류를 돌며
            int count = hashMap.get(num);
            int beforeSize = result.size();//현재까지의 List 개수를 파악

            for (int i = 0; i < beforeSize; i++) {//각 부분집합에 대해
                for (int j = 1; j <= count; j++) {//해당 숫자의 출현 개수만큼
                    List<Integer> temp = new ArrayList<>(result.get(i));//기존 부분집합을 복제한 다음

                    for (int k = j; k > 0; k--) {//해당 숫자를 추가
                        temp.add(num);
                    }

                    result.add(temp);//결과에 새로운 부분집합을 추가
                }
            }
        }

        return result;
    }
}

결과