HackkerRank - Sherlock and Array, Marc's Cakewalk, Grid Challenge, Maximum Perimeter Triangle

---

[풀이 - Sherlock and Array] : <Easy / 80.53%>

string balancedSums(vector<int> arr)
{
    int left = 0, right = 0, total = 0;
    //
    if(arr.size() == 1)
        return "YES";
    //
    for(int i = 0; i < arr.size(); ++i)
        total += arr[i];
    //
    for(int i = 0; i < arr.size(); ++i)
    {
        if(i-1 >= 0)
            left += arr[i-1];
        right = total - left - arr[i];
        if(left == right)
            return "YES";
    }
    //
    return "NO";
}

 

---

[풀이 - Marc's Cakewalk] : <Easy / 96.17%>

long marcsCakewalk(vector<int> calorie)
{
    long result = 0;
    //
    sort(calorie.begin(), calorie.end(), greater<int>());
    int count = calorie.size();
    for(int i = 0; i < count; ++i)
        result += pow(2, i) * calorie[i];
    //
    return result;
}

 

---

[풀이 - Grid Challenge] : <Easy / 83.22%>

string gridChallenge(vector<string> grid)
{
    int row = grid.size();
    int col = grid[0].length();
    //
    for(int i = 0; i < row; ++i)
        sort(grid[i].begin(), grid[i].end());
    //
    for(int i = 1; i < row; ++i)
    {
        for(int j = 0; j < col; ++j)
        {
            int value = grid[i][j] - grid[i-1][j];
            if(value < 0)
                return "NO";
        }
    }
    //
    return "YES";
}

 

---

[풀이 - Maximum Perimeter Triangle] : <Easy / 90.57%>

long CheckTriangle(vector<int> arr)
{
    sort(arr.begin(), arr.end());
    if((long)arr[2] >= (long)arr[0] + (long)arr[1])
        return -1;
    else
        return ((long)arr[0] + (long)arr[1] + (long)arr[2]);
}
//
void Combination(vector<vector<int>>& result, vector<int> arr, int count)
{
    result.clear();
    //
    int size = arr.size();
    vector<bool> v(size, true);
    for(int i = 0; i < size - count; ++i)
        v[i] = false;
    //
    do
    {
        vector<int> temp;
        for(int i = 0; i < size; ++i)
            if(v[i] == true)
                temp.push_back(arr[i]);
        //
        result.push_back(temp);
    } while (next_permutation(v.begin(), v.end()));
}
// Complete the maximumPerimeterTriangle function below.
vector<int> maximumPerimeterTriangle(vector<int> sticks)
{
    vector<int> result;
    // create combinations
    vector<vector<int>> combinations;
    Combination(combinations, sticks, 3);
    // check triangle
    long maxPerimeter = -1;
    int maxIdx = 0;
    for(int i = 0; i < combinations.size(); ++i)
    {
        long perimeter = CheckTriangle(combinations[i]);
        if(perimeter > maxPerimeter)
        {
            maxPerimeter = perimeter;
            maxIdx = i;
        }
    }
    
    if(maxPerimeter == -1) // no result
        result.push_back(-1);
    else // check max perimeter
    {
        sort(combinations[maxIdx].begin(), combinations[maxIdx].end());
        result = combinations[maxIdx];
    }
    //
    return result;
}