[LeetCode C++] 740. Delete and Earn

⭐️ 난이도

 

Medium

---

⭐️ 문제

https://leetcode.com/problems/delete-and-earn/

Delete and Earn - LeetCode

정수형 배열 nums가 주어진다.

주어진 연산(operation)을 여러 번 실행하여 얻을 수 있는 포인트를 최대로 하려고 한다.

[연산(operation)] 

1) 아무 nums[i]를 고르고 지우면, nums[i]만큼의 포인트를 얻을 수 있다.

2) 이후에는 nums[i]-1과 nums[i]+1에 해당하는 모든 수를 제거 한다.

 

위 연산과정을 거치면서 얻을 수 있는 최대의 포인트를 구하시오.

 

---

⭐️ Follow-up

 

X

 

---

⭐️ Idea flow

 

이전에 풀어봤던 DP문제들과는 다른 양상으로 보여서 당황했다.

예시를 통해서 확인을 해보니 빈도 수가 높은 수들을 잘 이용해야 할 것 같은데, nums[i]-1과 nums[i]+1을 지우는 것을 어떻게 처리해야 할지 도통 감이 오질 않았다.

 

결국 Discuss 게시판에서 도움을 받았다.

 

여기서 문제를 풀기 위한 중요한 포인트는 두 가지인데,

1. 많은 포인트를 얻으려면 (빈도 수 * nums[i])이 높은 값을 고르면 된다는 것

2. nums[i]-1과 nums[i]+1을 지워야 한다는 것은 곧, 인접한 값을 사용하지 못한다는 것이고

   그 말은 앞에서 풀었던 House Robber과 같은 조건이 되는 것이다.

 

전체적인 알고리즘은 다음과 같다.

1. nums 배열을 돌면서 unordered_map 혹은 vector 컨테이너에 (빈도수 * nums[i])값을 저장

   동시에 nums 배열에서 나타나는 가장 큰 수가 무엇인지 저장

2. 가능한 경우의 수는 두 가지이다.

   첫 번째로는 이전 수를 사용하면서 자기 자신은 사용하지 않는 것.

   두 번째로는 이전 수를 사용하지 않으면서 자기 자신을 사용하는 것.

   for문을 돌면서 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])을 구한다.

3. dp[max_val]을 반환한다.

 

 

---

⭐️ Code

 

[unordered_map 사용]

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int len = nums.size();
        int max_val = 0;
        
        unordered_map<int, int> hashmap;
        
        // hashmap[i]: i * 빈도수
        for(int i = 0; i < len; i++){
            hashmap[nums[i]] += nums[i];
            if(max_val < nums[i]) max_val = nums[i];
        }
        vector<int> dp(max_val + 1, 0);
        
        if(hashmap.count(1) != 0)
            dp[1] = hashmap[1];
        
        for(int i = 2; i <= max_val; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + hashmap[i]);
        }
        
        return dp[max_val];
    }
};

 

[vector 사용]

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        int len = nums.size();
        int max_val = *max_element(nums.begin(), nums.end());
        
        vector<int> frequency(max_val + 1);
        
        for(int i = 0; i < nums.size(); i++){
            frequency[nums[i]] += nums[i];
        }
        
        vector<int> dp(max_val + 1, 0);
        dp[1] = frequency[1];
        for(int i = 2; i <= max_val; i++){
            dp[i] = max(dp[i - 1], dp[i - 2] + frequency[i]);
        }
        
        return dp[max_val];
    }
};

 

---

⭐️ Feedback

 

1. 조건에 대해서 더 생각해보기

   nums[i]-1과 nums[i]+1을 지워야 한다는 말은 곧 해당 값들을 사용하지 못한다는 뜻으로 해석할 수 있다.

   문제에서는 항상 문제를 풀기 위한 힌트를 주며 그것들을 잘 찾아야 한다!

 

 

2. *max_element()

   C++에서는 *max_element와 *min_element를 지원하며 #include<algorithm>에서 제공한다.

   STL 컨테이너에 있는 값들 중 가장 큰 값과 가장 작은 값을 반환하는 함수이다.

   iterator(반복자)를 매개변수로 전달하여 원하는 범위 안에서 가장 큰(작은) 값을 찾을 수 있고, iterator를 반환한다.

 

   모든 요소에 접근을 해야 하기 때문에 시간 복잡도는 O(n)이다.