2610. Convert an Array Into a 2D Array With Conditions

• 문제 설명을 요약하면 배열에 있는 숫자를 다음과 같은 조건을 만족하는 set으로 묶는 방법을 찾는 것이다.
• 각 set에 포함된 숫자는 중복된 것이 없어야 한다.
• set의 숫자가 최소가 되는 조합을 찾아야 한다.

• 배열에 있는 숫자의 출현빈도를 세는 방식으로 해결할 수 있다.
• 조건을 보면 배열에 포함된 숫자의 범위는 1 부터 배열의 길이까지이다. 이점을 이용하여 배열 숫자의 출현 빈도를 셀 수 있는 메모리 공간 counter을 할당한다.
• 배열에 있는 모든 숫자의 출현 빈도를 센다.
• 모든 숫자를 처리할 때까지 다음 작업을 반복한다.
• 새로운 set을 할당한다.
• 각 숫자 i의 출현 빈도를 확인하여 출현 빈도 값 count[i]이 0이 아니라면 set에 넣고 출현 빈도 값을 1 감소 시킨다.

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        int[] counter = new int[nums.length + 1];
        int allCount = 0;
        for (int num : nums) {
            ++counter[num];
            ++allCount;
        }
        List<List<Integer>> result = new ArrayList<>();
        while (allCount > 0) {
            List<Integer> subResult = new ArrayList<>();
            for (int i = 0; i < counter.length; ++i) {
                if (counter[i] > 0) {
                    --counter[i];
                    --allCount;
                    subResult.add(i);
                }
            }
            result.add(subResult);
        }
        return result;
    }
}

• 또는 별도의 메모리 공간 없이 배열을 정렬한 뒤 출현 빈도 count에 따라 해당되는 set에 넣는 방법도 있다.
• 배열의 크기 조건 1 ≤ nums.length ≤ 200 이 매우 작아서 사실 메모리 공간 면에서 별로 이점은 없고 실행 시간 면에서 약간 불리하다.

class Solution {
    public List<List<Integer>> findMatrix(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int prev = -1;
        int count = 0;
        Arrays.sort(nums);
        for (int num : nums) {
            if (prev != num) count = 0;
            if (result.size() == count)
                result.add(new ArrayList<>());
            result.get(count++).add(num);
            prev = num;
        }
        return result;
    }
}