100일 (2491. Divide Players Into Teams of Equal Skill) two pointers

You are given a positive integer array skill of even length n where skill[i] denotes the skill of the ith player. Divide the players into n / 2 teams of size 2 such that the total skill of each team is equal.

The chemistry of a team is equal to the product of the skills of the players on that team.

Return the sum of the chemistry of all the teams, or return -1 if there is no way to divide the players into teams such that the total skill of each team is equal.

 

Example 1:

Input: skill = [3,2,5,1,3,4]
Output: 22
Explanation: 
Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6.
The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9 = 22.

Example 2:

Input: skill = [3,4]
Output: 12
Explanation: 
The two players form a team with a total skill of 7.
The chemistry of the team is 3 * 4 = 12.

Example 3:

Input: skill = [1,1,2,3]
Output: -1
Explanation: 
There is no way to divide the players into teams such that the total skill of each team is equal.

 

Constraints:

• 2 <= skill.length <= 10^5
• skill.length is even.
• 1 <= skill[i] <= 1000

 

- 접근방법

 

Example1을 예시로 들면

1. 주어진 배열을 오름차순 정렬한다. (325134 →123345),

2 .모든 양 끝단의 합이 같다면 ((1,5) (2,4) (3,3) 합의 6으로 전부 같다), answer += (1*5) + (2*4)  + (3*3)를 리턴한다.

3. 모든 양 끝단의 합이 같지않다면 -1을 리턴한다.

 

 

- 코드

class Solution {
    public long dividePlayers(int[] skill) {
        Arrays.sort(skill); // 1
        int ptr1 = 1;
        int ptr2 = skill.length-2;
        int teamSkill = skill[ptr1-1] + skill[ptr2+1];
        long answer = ((long) skill[ptr1 - 1] * skill[ptr2+1]);

        if(skill.length == 2) return answer;

        while(ptr1 < ptr2) {
            if(teamSkill == skill[ptr1] + skill[ptr2]) { 
                answer += ((long) skill[ptr1] * skill[ptr2]); // 2
            }
            else return -1; // 3

            ptr1++;
            ptr2--;
        }

        return answer;
    }
}

 

투 포인터를 이용하여 주어진 접근방법을 코드로 구현하면 다음과 같다.

 

 

 

 

https://leetcode.com/problems/divide-players-into-teams-of-equal-skill

Divide Players Into Teams of Equal Skill - LeetCode