101일 (2410. Maximum Matching of Players With Trainers) two pointers

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions.

 

Example 1:

Input: players = [4,7,9], trainers = [8,2,5,8]
Output: 2
Explanation:
One of the ways we can form two matchings is as follows:
- players[0] can be matched with trainers[0] since 4 <= 8.
- players[1] can be matched with trainers[3] since 7 <= 8.
It can be proven that 2 is the maximum number of matchings that can be formed.

Example 2:

Input: players = [1,1,1], trainers = [10]
Output: 1
Explanation:
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.

 

Constraints:

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

 

 

- 접근방법

트레이너가 가르칠 수 있는 플레이어의 최댓값을 구해야하므로 가장 최적화된 조건은

(트레이너 - 플레이어)가 최솟값이 되어야한다.

 

트레이너와 플레이어의 기량 가장 적게 매칭시키기 위해

1. players와 trainers를 오름차순 정렬을 한다.

2. player <= trainer의 경우를 순차적으로 찾아서 리턴하면 된다. (오름차순 정렬로 최적화는 되었음)

→ 포인터를 활용하여 조건에 만족하는 경우를 순차적으로 찾으면 된다.

 

 

- 코드 

class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        int answer = 0;
        int ptr1 = 0;
        int ptr2 = 0;

        Arrays.sort(players); // 1
        Arrays.sort(trainers);

        while(true) {
            if(trainers.length == ptr2 || players.length == ptr1) break; // basecase

            if(players[ptr1] <= trainers[ptr2]) { // 2. pointer 활용
                answer++;
                ptr1++;
            } 
            
            ptr2++;
        }

        return answer;
    }
}

 

매치되는 최댓값을 구하기 위해서는 min(트레이너 - 플레이어) >= 0 을 찾아야하는데

players와 trainers를 오름차순 정렬하므로 간단하게 정리하였다.

 

 

 

 

https://leetcode.com/problems/maximum-matching-of-players-with-trainers/

Maximum Matching of Players With Trainers - LeetCode