HackerRank - Cut the sticks, Non-Divisible Subset, Equalize the Array, Queen's Attack II

---

[풀이 - Cut the sticks]

int GetLengthOfCut(vector<int> arr)
{
    int result = INT_MAX;
    //
    for(int i = 0; i < arr.size(); ++i)
    {
        if(arr[i] < result)
            result = arr[i];
    }
    //
    return result;
}

vector<int> cutTheSticks(vector<int> arr)
{
    vector<int> result;
    while(true)
    {
        int sticksCut = arr.size();
        //
        if(sticksCut == 0)
            break;
        else
            result.push_back(sticksCut);
        //
        int lengthOfCut = GetLengthOfCut(arr);
        //
        auto iter = arr.begin();
        for(; iter != arr.end(); )
        {
            *iter -= lengthOfCut;
            if(*iter <= 0)
                arr.erase(iter);
            else
                ++iter;
        }
    }
    return result;
}

 

---

[풀이 - Non-Divisible Subset]

int nonDivisibleSubset(int k, vector<int> s)
{
    int result = 0;
    int count = s.size();
    map<int, int> m;
    // convert array to map of remain
    for(int i = 0; i < count; ++i)
    {
        int remain = s[i] % k;
        m[remain]++;
    }
    //
    for(int i = 1; i <= (k/2); ++i)
    {
        if(i != k-i) // case1: many of remain : (1 > k-1), (2 < k-2) ...
            result += max(m[i], m[k-i]);
        else // case2: remain == k/2
        {
            if(m[i] > 0)
                result++;
        }
    }
    // case3: remain == 0
    if(m[0] > 0)
        result++;
    //
    return result;
}

1. (a + b) % x 가 '0'인 경우 (a % x) + (b % x) 또한 '0'이다.

 

2. 두 숫자의 합이 x의 배수가 되지 않게 하려면 두 숫자의 나머지의 합이 x가 아니어야 한다.

   ex) (1, x-1), (2, x-2)와 같은 조합이 아닐 것.

 

3. 배열의 부분 집합 중 임의의 2개의 원소의 합이 x의 배수가 되지 않는

   부분집합의 수를 최대로 하기 위해 나머지가 i인 원소와 x-i인 원소의 갯수를 비교하여, 큰 것을 담는다.

 

---

[풀이 - Equalize the Array]

int equalizeArray(vector<int> arr)
{
    int result = 0;
    // Set Array To Map
    map<int, int> m;
    for(int i = 0; i < arr.size(); ++i)
        m[arr[i]]++;
    // Find Max (Key & Value)
    pair<int, int> max;
    auto iter = m.begin(), end = m.end();
    for(; iter != end; ++iter)
    {
        if(iter->second > max.second)
        {
            max.second = iter->second;
            max.first = iter->first;
        }
    }
    // Sum Values except Max
    iter = m.begin();
    for(; iter != end; ++iter)
    {
        if(iter->first != max.first)
            result += iter->second;
    }
    //
    return result;
}

 

---

[풀이 - Queen's Attack II]

const int dirCount = 8;
//
int queensAttack(int n, int k, int r_q, int c_q, vector<vector<int>> obstacles)
{
    int dist[dirCount];
    // cross dirs left To Clockwise
    dist[0] = c_q - 1;
    dist[1] = n - r_q;
    dist[2] = n - c_q;
    dist[3] = r_q - 1;
    // diagonal dirs LU To ClockWise
    dist[4] = min(dist[0],dist[1]);
    dist[5] = min(dist[1],dist[2]);
    dist[6] = min(dist[2],dist[3]);
    dist[7] = min(dist[3],dist[0]);
    //
    int x, y;
    for(int i = 0; i < k; ++i)
    {
        y = obstacles[i][0] - r_q;
        x = obstacles[i][1] - c_q;
        if(x == 0)
        {
            if(y > 0)
                dist[1] = min(dist[1], +(y-1));
            else
                dist[3] = min(dist[3], -(y+1));
        }
        else if(y == 0)
        {
            if(x > 0)
                dist[2] = min(dist[2], +(x-1));
            else
                dist[0] = min(dist[0], -(x+1));
        }
        else
        {
            float m = (float)y / (float)x;
            if(m == 1.0)
            {
                if(x > 0)
                    dist[5] = min(dist[5], +(x-1));
                else
                    dist[7] = min(dist[7], -(y+1));
            }
            else if(m == -1.0)
            {
                if(x > 0)
                    dist[6] = min(dist[6], +(x-1));
                else
                    dist[4] = min(dist[4], +(y-1));
            }
            else
                continue;
        }
    }
    //
    int result = 0;
    for(int i = 0; i < dirCount; i++)
        result += dist[i];
    //
    return result;
}