[LeetCode] 2491. Divide Players Into Teams of Equal Skill

https://leetcode.com/problems/divide-players-into-teams-of-equal-skill/description/?envType=daily-question&envId=2024-10-04

leetcode - Divide Players Into Teams of Equal Skill

문제 유형 : 정렬, 그리디, 투 포인터

문제 난이도 : Medium

 

문제

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.

 

짝수 n의 길이만큼의 크기의 양의정수배열 skill이 주어진다.

skill[i]는 i번째 선수의 기술력을 나타낸다.

n/2개의 짝을 지어서 각 짝의 합이 같게 하라.

그 다음, 각 팀의 짝들을 곱해서 모두 더한 값을, 케미스트리라 하는데, 그 케미스트리를 반환해라.

불가능하면 -1을 반환해라.

 

풀이

정렬하고, 첫 양 끝의 합을 구한다. 이 합이 기준이 될 것이다.

왼쪽과 오른쪽 양 끝에서 중앙으로 좁히면서, 첫 양끝의 값과 똑같은지 확인하고, 안되면 -1을 반환하고, 맞으면 두 값의 곱을 누적시킨다.

누적값을 반환한다.

 

코드

C++

class Solution {
public:
    long long dividePlayers(vector<int>& skill) {
        sort(skill.begin(), skill.end());
        int left = 0, right = skill.size()-1;
        int total = skill[left] + skill[right];
        long long ans = skill[left++] * skill[right--];
        
        while(left < right) {
            if(total != skill[left] + skill[right]) return -1;
            ans += skill[left++] * skill[right--];
        }

        return ans;
    }
};