Level 2. 혼자 놀기의 달인

Level 2. 혼자 놀기의 달인

 

 

유니온-파인드의 Find를 응용해 해결할 수 있다.

• 상자를 열어 숫자를 확인해가는 과정이 유니온-파인드에서 대표 번호를 찾는 과정과 같기 때문이다.

 

Find 과정에서 현재 집합에 속하는 숫자의 개수를 갱신하고, 다음 대표 번호를 찾기 전에 내 대표 번호를 자신으로 설정해주면 된다.

 

모든 수들이 하나의 집합에 속할 경우는, 두 번째 집합의 크기가 0임에 주의해야 한다.

 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int findRep(vector<int>& rep, int i, int& depth)
{
    if (rep[i] == i)
    {
        depth = max(1, depth);

        return i;
    }

    ++depth;

    int next = rep[i];
    rep[i] = i;

    return rep[i] = findRep(rep, next, depth);
}

int solution(vector<int> cards)
{
    size_t n = cards.size() + 1;
    vector<int> rep(n, 0), numbers;
    unordered_map<int, bool> group;

    copy(cards.begin(), cards.end(), rep.begin() + 1);

    for (int i = 1; i < n; ++i)
    {
        if (group[rep[i]] == false)
        {
            int nNum = 0;

            group[findRep(rep, i, nNum)] = true;
            numbers.emplace_back(nNum);
        }
    }

    sort(numbers.rbegin(), numbers.rend());

    return (numbers.size() <= 1) ? 0 : numbers[0] * numbers[1];
}