[leetcode] 870. Advantage Shuffle

https://leetcode.com/problems/advantage-shuffle/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

주어진 nums1 배열에서 조건에 맞는 permutation 을 찾아 반환하는 문제이다. 

 

---

 

사용할 샘플 예제는 아래와 같다.

nums1 = [12, 24, 8, 32], nums2 = [13, 25, 32, 11]

 

Approach: Greedy with two pointers

1. nums1 을 오름차순 정렬한다.

2. nums2 을 오름차순 정렬한다. 이때, 기존 인덱스를 저장하고 있어야한다. 결과적으로 input 으로 주어진 nums2 의 순서는 바뀌면 안 되기 때문이다.

3. Two Pointer 개념을 이용해 nums1 에 left, right 포인터를 세팅한다.

• left 값 = nums1 에서 가장 작은 값
• right 값 = nums1 에서 가장 큰 

4. nums2 에서 거꾸로 loop 를 돌며, 자기보다 큰 수가 없으면 left 가 가리키고 있는 값을 채택한다.

왜냐하면 nums2 입장에서 자기보다 큰 수가 없는 상황에서는 nums1 중 가장 작은 값인 left 를 채택해야, 문제에서 말하는 "advantage" 를 maximize 할 수 있기 때문이다.

 

 

5. nums2 입장에서 자기보다 큰 수가 있으면 right 가 가리키고 있는 값을 채택한다.

 

---

Python 코드

from typing import List


class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        # nums2 를 정렬할 때는, 기존 인덱스도 같이 저장하며 정렬한다.
        indexed_nums2 = sorted((num, i) for i, num in enumerate(nums2))

        result = [0] * len(nums1)

        left, right = 0, len(nums1) - 1

        for num2, original_index in indexed_nums2[::-1]: 
            if nums1[right] > num2:
                # nums1 에서 가장 큰 값을 세팅한다.
                result[original_index] = nums1[right]
                right -= 1  
            else:  
                # nums1 에서 가장 작은 값을 세팅한다.
                result[original_index] = nums1[left]
                left += 1

        return result

 

 

---

 

 

이 문제를 보고 Greedy 알고리즘을 사용해야 한다는 것을 어떻게 알 수 있는가?

항상 nums2 보다 큰 nums1의 요소를 선택하는게 "최적의 선택" 이라는 점에서 Greedy 함을 발견할 수 있다.