[2024] Day4. 2870. Minimum Number of Operations to Make Array Empty

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 4일 (목)
Leetcode daily problem

2870. Minimum Number of Operations to Make Array Empty

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/?envType=daily-question&envId=2024-01-04

Problem

양의 정수로 구성된 배열 num이 주어질 때,
동일한 값을 가진 두 요소를 선택하고 배열에서 삭제하거나, 동일한 값을 가진 세 개의 요소를 선택하고 배열에서 삭제하는 두 가지 작업이 가능하다.
배열을 비우는데 필요한 최소 작업 수를 반환하거나, 배열을 완전히 비우기 어려운 경우 -1을 반환한다.

Solution

주어진 배열 내의 고유한 숫자에 따라서 Counter를 사용해 빈도수를 파악한다.
그리고 Counter로 파악한 고유 숫자 대비 빈도수에 대해서 루프를 돌면서, 빈도수가 1이면 삭제할 수 없으므로 완전히 배열을 비우기 어려우므로 1를 반환하고, 해당 빈도수를 3으로 나눴을 때의 정수값 (math.ceil)을 이용해서 필요한 작업수를 계산하여 최종 작업 수를 리턴한다.

Code

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        ans = 0

        for n,c in cnt.items():
            if c == 1:
                return -1

            ans += math.ceil(c/3)

        
        return ans

Complexicity

시간 복잡도

Counter(nums)를 사용하여 리스트의 각 숫자의 빈도수를 계산하는 데 O(n)의 시간이 소요되고,
for loop에서 nums에 나온 고유한 숫자를 m이라고 했을 때 O(m)의 시간이 소요된다.
즉, 전체 시간 복잡도는 O(n+m) 이다.

공간 복잡도

Counter(nums)를 저장할 때, 고유한 숫자의 수를 m이라고 했을 때 공간복잡도는 O(m)이다.

이 코드의 시간 복잡도와 공간 복잡도는 배열의 크기와 고유한 숫자의 개수에 비례한다.