[코테연습] 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

 

- 문제분석

1. int[] skill 배열이 있고, 내부에는 짝수 length 의 양수값이 들어있다.

2. skill의 각 원소 2개를 더했을때, 모두 동일한 값으로 출력되어야한다.

3. 이때, 동일한 값을 곱한 값을 모두 더한 값을 리턴해라 ( skill[i] * skill[i] + ... + )

 

- 문제풀이

> 투포인터 개념 미사용

 

1. skill 배열의 length 값을 2로 나누어 k 값을 정의한다. 

1-1. 해당 값은 총 원소 값의 평균을 찾을 수 있는 분모값으로 정의한다.

2. skill 배열의 원소를 모두 더한다.

2-1. 더한 값을 k 로 나누어 평균 값을 구한다. ( sum / ( skill.length / 2 ) )

3. HashMap 을 초기화하여 해당 map 에 모든 skill 원소를 넣는다.

3-1. key 는 원소값 value 는 원소값의 갯수로 정의한다.

4. skill 배열을 반복문으로 반복한다.

4-1. skill 배열의 임의의 원소 skill[i] 를 꺼내, map 에 있는지 여부를 확인한다.

4-2. map 에 있을 경우 평균값 - 원소값 을 계산하여 필요한 원소값을 구한다.

4-3. 필요한 원소값의 여부를 map 에서 확인한다.

4-4. map 에 있을 경우 해당 값을 곱한 값을 더하여 리턴한다.

4-5. map 에 없을 경우 -1 을 리턴한다.

 

class Solution {
    /**
    int k = skill.length / 2;
    
    [][][]
    [3][2][5]

    3 + 2 + 5 + 1 + 3 + 4 = 18 / 3 = 6

    [3] [2,5,1,3,4]

    search in map

    1 + 1 + 2 + 3 = 7 / 2 = x


    
     */
    public long dividePlayers(int[] skill) {
        int k = skill.length / 2;

        Map<Integer, Integer> map = new HashMap<>();

        int sum = 0;
        for(int num : skill) {
            map.put(num, map.getOrDefault(num, 0)+1);
            sum+=num;
        }

                
        if (sum % k != 0) {
            return -1;
        }

        int equalsNumber = sum / k;

        long cal = 0;
        for (int i = 0; i < k; i++) {
            int num = skill[i];
            
            
            if (map.get(num) == 0) {
                k+=1;
                continue;
            }
            int rem = equalsNumber - num;
            map.put(num, map.get(num) - 1);

            if (map.get(rem) == null || map.get(rem) == 0) {
                return -1;
            } else {
                map.put(rem, map.get(rem)-1);
            }
            cal += (num * rem);
        }

        return cal;
    }
}

 

 

> 투포인터 개념 사용

1. skill 배열을 Arrays.sort 로 오름차순 정렬한다.

2. left 인덱스를 0 으로, right 인덱스를 skill.length-1 로 초기화한다.

3. 평균값을 skill[left] + skill[right] 로 정의한다.

4. while 문으로 반복하여 left 가 right 보다 작을 때 까지, skill[left] + skill[right] 를 한다.

5. 만약 평균값과 다르다면 -1 을 리턴하고, 같다면 left++, right-- 을 하여 두개의 포인터가 서로 가까워지도록 반복한다.

 

class Solution {
    public long dividePlayers(int[] skill) {
        
        int left = 0;
        int right = skill.length-1;

        Arrays.sort(skill);

        int equalsNum = skill[left] + skill[right];
        long rs = 0;
        while(left < right) {
            if (equalsNum != (skill[left] + skill[right])) {
                return -1;
            }
            rs += (long) skill[left] * skill[right];
            left++;
            right--;
        }

        return rs;
    }
}