[Array/String][Easy] 1431. Kids With the Greatest Number of Candies

https://leetcode.com/problems/kids-with-the-greatest-number-of-candies

Kids With the Greatest Number of Candies - LeetCode

 

Q. 배열의 수만큼의 사탕의 각 index가 가지고 있을때, extraCandies를 더하면 각 index가 최대의 수가 될지를 반환하라.

 

Key : 그냥 생각하면, 각 수에 해당 추가캔디수를 더하고, 해당 수가 최대값인지 sort나 loop를 돌면서 판단하면 된다. 그러면 O(NxN)의 time complexity가 소요되므로, 조금더 정리가 필요. 

         우선 배열의 최대값을 구하고, 각 배열의 수가 extraCandies가 더해졌을때, 최대값이 될지를 판단하면 최적화가 된다. 

 

vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies)
{
    // input array가 각 아이들이 가지고 있는 사탕의 수다. 이때 extranCadies를 각 수에 더하면, 
    // 각 해당 아이가 전체 에서 최대의 사탕수를 가지는지 여부를 반환하라.
    // 이때 여러 아이가 동시에 최대의 캔디수를 가질 수 있다.
    //
    int maxC = 0;
    for (int k = 0; k < candies.size(); ++k)
        maxC = max(maxC, candies[k]);

    vector<bool> vRet;
    for (int k = 0; k < candies.size(); ++k)
    {
        vRet.push_back(candies[k] + extraCandies >= maxC);
    }
    return vRet;
}

 

Time Complexity : O(N)

Comment : 최적화에 도달하기 위한 사고의 초석에 해당하는 문제.