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

https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/description/

Minimum Number of Operations to Make Array Empty - LeetCode

leetcode - Minimum Number of Operations to Make Array Empty

문제 유형 : 해시, 그리디

문제 난이도 : Medium

 

 

문제

You are given a 0-indexed array nums consisting of positive integers.

There are two types of operations that you can apply on the array any number of times:

• Choose two elements with equal values and delete them from the array.
• Choose three elements with equal values and delete them from the array.

Return the minimum number of operations required to make the array empty, or -1 if it is not possible.

 

양의 정수로 이루어진 정수 배열 nums가 주어진다.

두 가지의 연산을 당신은 얼마든지 할 수 있다.

• 두 개의 같은 값을 가진 요소를 골라 배열에서 삭제
• 세 개의 같은 값을 가진 요소를 골라 배열에서 삭제

배열을 빈 배열로 만드는 최소 연산의 수를 구하시오.

불가능하면 -1을 반환하시오.

 

풀이

map을 이용하여 숫자-개수 형태로 저장시킨다.

 

각 숫자의 개수별로 없애는 경우의 수를 구하는 알고리즘은 다음과 같다:

우선, 개수가 1인 경우 -1을 반환한다. 불가능한 경우이기 때문이다.

숫자의 개수를3으로 나눈 값을 총합에 누적시킨다.(무작정 3개씩 없애기)

거기에, 나머지가 있는 경우 1을 추가로 더한다.

• 나머지 2: 두 개씩 없애는 연산을 한 번 실행 가능
• 나머지 1: 3개씩 없앤 연산을 한 번 덜 하고, 두 개씩 없애는 연산을 두 번 한것으로 간주.(3 + 1 = 4)

총합을 반환해주면 된다.

 

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> mp;
        int cnt = 0;
    
        for(const auto &num : nums) {
            mp[num]++;
        }

        for(const auto &val : mp) {
            int amount = val.second;
            if(amount == 1) return -1;
            cnt += amount/3;
            if(amount%3 > 0) cnt++;
        }

        return cnt;
    }
};

hash table

<컴퓨터>해시표(~表)