2870. Minimum Number of Operations to Make Array Empty

• 배열에서 동일한 숫자를 2개 또는 3개씩 묶어서 제거하는 작업을 수행할 수 있을 때 배열을 빈 상태로 만들기 위해 필요한 최소의 작업 수는 얼마인지 구하는 문제이다.

• 각 숫자별로 출현 빈도를 세어서 저장하는 방법도 있겠지만 별도의 메모리 공간을 사용해야 한다.

• 배열을 정렬하여 연속된 동일 숫자를 세면 별도의 메모리 공간 없이 문제를 풀 수 있다.

• 조금 헷갈렸던 부분은 2개씩 묶은 작업의 수, 3개씩 묶은 작업의 수를 어떻게 세어야 하는지에 대한 것이었다.
• 가능하다면 3개씩 묶어서 제거하는 것이 최소의 작업 수를 달성하는데 유리하다. 따라서 단순하게 생각하면 3개씩 묶어서 제거한 뒤 나머지 숫자를 2개씩 제거하면 된다.
• 하지만 3개씩 묶어서 제거했을 때 2개가 남지 않는 경우는 어떻게 해야 될까?
• 출현빈도 % 3 == 2: 나머지가 2이므로 작업의 숫자를 하나 더해주면 된다.
• 출현빈도 % 3 == 1: 나머지가 1이므로 기존에 3개씩 묶어서 한 작업 하나를 취소한다. 그러면 남은 숫자가 4이므로 2개씩 묶어서 2번 제거하면 된다. 하지만 결국 따져보면 작업의 숫자를 하나 더해주는 것과 같다.
• 결론적으로 출현빈도 % 3 ≠ 0 이라면 작업 숫자를 하나 늘려주면 된다.

class Solution {
    int countToOps(int count) {
        if (count == 1) return -1;
        int ops = count / 3;
        if (count % 3 != 0) ++ops;
        return ops;
    }

    public int minOperations(int[] nums) {
        int result = 0;
        int prev = 0;
        int count = 0;
        Arrays.sort(nums);
        for (int num : nums) {
            if (prev != num) {
                int ops = countToOps(count);
                if (ops == -1) return -1;
                result += ops;
                count = 0;
            }
            prev = num;
            ++count;
        }
        if (count > 0) {
            int ops = countToOps(count);
            if (ops == -1) return -1;
            result += ops;
        }
        return result;
    }
}