[Heap/Priority Queue][Medium] 2542. Maximum Subsequence Score

https://leetcode.com/problems/maximum-subsequence-score

Maximum Subsequence Score - LeetCode

 

Q. 길이가 같은 두개의 배열과 양수 k 가 주어질 때, 두 배열에서 k의 길이가 되는 부분열을 취한다. 

 이때 nums1에서는 그 합을, nums2에서는 부분열의 최소값을 가지고 두 수를 곱한다. 

 이 곱의 최대값을 찾아라.

 

 

Solution. 

 조금 생각해 봐야 할 문제다. 

 첫 배열에서는 부분열의 전체합을, 두번째 배열에서는 부분열의 최소값을 가지고 최대 곱을 찾는다. 

 

 그렇다면 최대합을 기준으로 최소값을 걸러내며 값을 도출 할 것인가, 반대로 최소값을 가지고 상응하는 수들의 합을 가지고 결과를 도출할 것인가 하는 두개의 선택지가 나온다. 

 

첫번째 부터 생각해 보자. 

 

k 가 3정도 일때,

첫째열 값을 기준으로 정렬한다. 그래서 큰 sum에서 작은 sum으로 확장하는 방식으로 결과를 얻어 비교해 본다. 

예를 들어 10, 9, 8, 7, 6.. 정렬했더니 nums1이 이런 식이다. 

k가 3이므로 첫 연산에서 10, 9, 8의 합을 구하고 이에 상응하는 nums2에서 최소값과 곱한다. 

확장한다. 

다음 라운드에, 7을 포함한다. 그리고 k가 3이므로, 하나를 제거해야 하는데, 어떤 기준으로 제거해야 할까. 

상응하는 nums2에서 최소값을 가진 녀석의 nums1 값을 제거하면 될까?

아니면, 그냥 nums1에서 제일 첫번째 큰 값을 차례대로 제거해야 할까?

고민해 보자. 

 

다음으로 두번째를 생각해 본다.

역시 k가 3 정도 일때, 

nums2에서 min 값을 순차적으로 적용키 위해, nums2 값을 정렬한다.

예를 들면 역시 10, 9, 8, 7 .. 이면 k가 3이면 첫 연산에서 8까지 포함하게 되고 최소값은 8이다. 

10, 9, 8 에 해당하는 nums1에서의 sum을 구한다. 그렇게 첫번째 연산을 한다. 

확장한다. 

nums2를 7까지 확장하면 앞의 값을 볼 필요없이, 최소값은 7이 된다.

그렇다면 여기서는 어떤 녀석을 제거할까. 

두번째 라운드에서는 10, 9, 8 의 어떤 녀석을 제거해도 최소값이 7이 됨에는 변함이 없다. 따라서 이 값의 최종 결과를 결정하는 값은 상응하는 nums1에서의 합으로 결정된다. 

우리가 원하는 값은 이의 최대치 이므로, 제거해야 할 녀석은 nums1의 값중에 최소값을 제거하면 될 것이다. 

 

첫번째와 두번째 연산과정은 언듯 비슷하면서 다르다. 

min 값 위주로 정렬하고 확장하는 과정은 min 값이 k에 관계 없이 확정적이 되므로, 연산의 결과는 nums1의 sum을 어떻게 최대로 만드냐에 따라 결정된다. 

하지만, 첫번째 연산에서는 sum이 최대가 되도록 nums1을 정렬하고, 상응하는 nums2의 최소값을 곱하며 제거해 나가는 방식이다. 이는 양쪽 값에 모두 영향을 받으므로 더욱 복잡해 지며 예측키 어렵게 된다. 

간단하게, nums2를 min위주로 정렬하고 연산을 확장하는 것이 명료한 연산이라는 것이다. 

 

실제로 적용해 보자. 

 

nums1 

3, 4, 5, 6 

 

nums2

10, 9, 8, 7 

 

k=2일때, nums2 값 대로 내림차순 정렬했다고 가정한다.

 

위 연산대로 사고를 개진해 보자. 

10, 9 -> 최소값은 9다. 3, 4 의 합은 7, 즉 결과는 63이다. (3, 4 / 10, 9) 

10, 9, 8 -> 최소값은 8이다. 3혹은 4 그리고 5 이다. 결과가 최대여야 하므로, 3을 제거하면 sum은 9, 즉 결과는 72 이다. ( 4, 5 / 9, 8)

10, 9, 8, 7 -> 최소값은 7이다. nums2에서는 4, 5 중 작은 4를 제거한다. 7x11=77 이다. (8, 7 / 5, 6)

따라서 최종 최대값은 77 이 된다. 

 

핵심은 sum x min 에서 양변 중 고정할 수 있는 값을 찾으면, 나머지 다른쪽의 수를 개진하는 방법을 결정할 수 있으므로, 해당 방법을 따르는 것이다. 

 

이 문제는 훈련없이 직관이로 풀기는 조금 힘들어 보인다. 

많이 풀어봐야만 관련 패턴이 보이게 될 것이다. 

 

long long maxScore(vector<int>& nums1, vector<int>& nums2, int k)
{
    // min 을 결정지을 nums2를 우선 정렬한다. 
    map<int, vector<int>, greater<int>> mapBuff;	// Decending order.
    for (int q = 0; q < nums2.size(); ++q)
    {
        if (mapBuff.find(nums2[q]) == mapBuff.end())
        {
            vector<int> vTemp{ q };
            mapBuff[nums2[q]] = vTemp;
        }
        else
            mapBuff[nums2[q]].push_back(q);
    }

    long long ret = 0;
    long long sum = 0;
    priority_queue <int, vector<int>, greater<int> > qBuff;	// min heap.
    for (map<int, vector<int>>::iterator it = mapBuff.begin(); it != mapBuff.end(); ++it)
    {
        for (int q = 0; q < it->second.size(); ++q)
        {
            int idx = it->second[q];
            sum += nums1[idx];
            qBuff.push(nums1[idx]);

            if (qBuff.size() == k)
            {
                // k의 길이에 관계 없이, 최소값은 늘 마지막 값이다.
                int min = it->first;
                ret = max(ret, sum * min);

		// 이때 sum에서는 우리가 최대값을 구하려 하므로, sum에서 최소값을 제거한다.
                // 따라서 이 과정때문에 min heap이 필요하다.
                sum -= qBuff.top();
                qBuff.pop();
            }
        }
    }
    return ret;
}

 

 

 sort 대신 map을 썼지만, 다양한 방식으로 최적화 해 볼 여지는 있겠다.