[LeetCode] 2244. Minimum Rounds to Complete All Tasks

- Problem

2244. Minimum Rounds to Complete All Tasks

You are given a 0-indexed integer array tasks, where tasks[i] represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the same difficulty level.

Return the minimum rounds required to complete all the tasks, or -1 if it is not possible to complete all the tasks.

Example 1:

Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation: To complete all the tasks, a possible plan is:
- In the first round, you complete 3 tasks of difficulty level 2. 
- In the second round, you complete 2 tasks of difficulty level 3. 
- In the third round, you complete 3 tasks of difficulty level 4. 
- In the fourth round, you complete 2 tasks of difficulty level 4.  
It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.

Example 2:

Input: tasks = [2,3,3]
Output: -1
Explanation: There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.

Constraints:

- 1 <= tasks.length <= 10^5
- 1 <= tasks[i] <= 10^9

각 원소가 작업량을 나타내는 배열 tasks가 주어진다.
각 round마다 2개 혹은 3개의 작업을 끝낼 수 있고, 이 때 같은 난이도의 작업만 해결할 수 있다.
모든 작업을 끝낼 수 있는 최소 round를 반환하고, 만약 모든 작업을 끝내는 것이 불가능하다면 -1을 리턴한다.

---

- 내 풀이

key point는 만약 특정 원소의 빈도가 1이라면 -1을 리턴해야 한다는 것이다.
가령 [2,2,2,3]이라는 tasks가 주어질 경우 난이도 2의 작업은 총 3개이기에 요구사항에 맞게 한 라운드에 작업을 끝낼 수 있다. 하지만, 난이도 3의 작업은 한 개이기에 작업을 끝마칠 수 없다. 그러므로 -1을 리턴하게 된다.

또 다른 point는 공식 혹은 패턴이다.
예제와 함께 살펴 보자!

가령 1,2,3 난이도를 가지는 작업이 4,5,6개 있다고 해보자.
1난이도는 : 2 + 2 = 4로 나타낼 수 있다. 즉 2개의 round가 소요된다.
2난이도는 : 2 + 3 = 5로 나타낼 수 있다. 마찬가지로 2개의 round가 소요된다.
3난이도는 : 3 + 3 = 6으로 나타낼 수 있다. 역시 2개의 round가 소요된다.

이번에는 1,2,3 난이도를 가지는 작업이 7,8,9개 있다고 해보자.
1난이도는 : 2+2+3 = 7로 나타낼 수 있다.
2난이도는 : 2+3+3 = 8로 나타낼 수 있다.
3난이도는 : 3+3+3 = 9로 나타낼 수 있다.
7,8,9개가 있을 경우 총 3개의 라운드가 소요된다.

마지막으로 1,2,3 난이도를 가지는 작업이 10,11,12개 있다고 해보자.
1난이도 : 2+2+3+3 = 10
2난이도 : 2+3+3+3 = 11
3난이도 : 3+3+3+3 = 12
10,11,12개는 총 4개의 라운드가 소요된다.

이를 쭉 나열해보면 다음과 같은 공식을 발견할 수 있다.

• round = ⌈같은 난이도를 가진 task의 개수 / 3)⌉
  - ceil. 즉, 올림이다.

풀이 코드는 다음과 같다.

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        count_tasks = collections.Counter(tasks)
        answer = 0
        
        for task in count_tasks.values():
            if task == 1:
                return -1
            
            answer += math.ceil(task / 3)
        
        return answer

- short code

class Solution:
    def minimumRounds(self, tasks: List[int]) -> int:
        count_tasks = collections.Counter(tasks).values()
        
        if 1 in count_tasks: return - 1
        
        return sum([math.ceil(task / 3) for task in count_tasks])

풀이 방법은 다음과 같다.

1. 주어진 배열 tasks를 카운터를 활용하여 각 작업 난이도의 빈도 수를 계산한다.
2. 카운터의 값 리스트를 돌며 round의 총 개수를 계산한다. 이 때 값이 1이라면 -1을 리턴하고, 아니라면 위의 공식을 이용하여 round를 계산한다.

O(n)의 시간복잡도를 가지게 된다.

- 결과