[leetcode] 575. Distribute Candies

문제

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.
Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.
Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

n == candyType.length
2 <= n <= 104
n is even.
-105 <= candyType[i] <= 105

첫번째 코드

var distributeCandies = function(candyType) {
    let sum = 0;

    for (let i = 0; i < candyType.length; i++) {
        console.log(candyType[i - 1]);
        if (i > 0 && candyType[i] !== candyType[i - 1]) {
            sum = sum + 1;
        } else {
            continue;
        }
    }

    return sum;
};

에러

두번째 코드

/**
 * @param {number[]} candyType
 * @return {number}
 */
var distributeCandies = function(candyType) {
    let sum = 0;

    for (let i = 0; i < candyType.length; i++) {
        
        if (i > 0 && candyType[i] !== candyType[i - 1]) {
            sum = sum + 1;
        } else {
            continue;
        }
    }
    
    if (sum < candyType.length / 2) {
        return sum = sum + 1;
    } else {
        return sum
    }

};

에러

세번째 코드

function distributeCandies(candyType) {
    let sum = 0;
    const myCandy = [...new Set(candyType)];

    for (let i = 0; i < myCandy.length; i++) {

        if (i > 0 && myCandy[i] !== myCandy[i - 1]) {
            sum = sum + 1;
        } else {
            continue;
        }
    }

    if (sum < candyType.length / 2) {
        console.log(sum = sum + 1);
    } else if (sum > candyType.length / 2) {
        console.log(sum = sum - 1);
    } else {
        console.log(sum);
    }

};

흠 그냥 이렇게 푸는게 아니다 다시 천천히 풀어보자

네번째 코드

function distributeCandies(candyType) {
    let sum = 0;
    const myCandy = [...new Set(candyType)];

    if (myCandy.length >= candyType.length / 2) {
        console.log(candyType.length / 2);
    } else {
        for (let i = 0; i < myCandy.length; i++) {

            if (i > 0 && myCandy[i] !== myCandy[i - 1]) {
                sum = sum + 1;
            } else {
                continue;
            }
        }
    }
    if (sum < candyType.length / 2) {
        console.log(sum = sum + 1);
    } else {
        console.log(sum);
    }

};

// const candyType = [3, 1, 0, 4];
const candyType = [6, 6, 6, 6];
//const candyType = [1, 1, 2, 2, 3, 3];

distributeCandies(candyType);

정리

먼저 조건에 대해 생각해보았다. 사탕의 종류는 [1000, 1000, 1, 1, 2, 3, 4, 5] 이런식으로 나타날 수 있다.

전체 사탕의 갯수 : 8개
사탕의 종류 : 6개
먹을 수 있는 사탕의 갯수 : 4개 (전체 사탕 갯수 n / 2)

그럼 우리는 사탕의 종류와 먹을 수 있는 사탕의 갯수 둘 중 최소 값만 도출해 내면 된다.

const distributeCandies = CandyType => Math.min((new Set(CandyType)).size, CandyType.length / 2);

중복 값을 제거한 사탕 배열(candyType)의 사이즈와 먹을 수 있는 사탕의 갯수 / 2 중 최소값을 도출한다!