[Programmers] 혼자 놀기의 달인

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

 

---

 

문제 해결 과정

착안

문제에서 주어지는 숫자 카드의 배열에 대해, 숫자 카드들을 게임 규칙에 따라 그룹으로 나누는 방법은 유일하다. 따라서 그룹에 포함되지 않은 카드가 없을 때까지 카드들을 게임 규칙에 따라 그룹으로 나누고, 숫자 카드가 많은 그룹부터 내림차순으로 정렬해 상위 2 개의 카드 그룹의 수를 곱한 값을 출력한다.

 

구현

각 숫자 카드 별로 그룹에 포함되었는지의 여부를 표시하는 변수를 별도로 선언하여 활용하였고, 모든 숫자가 하나의 그룹에만 포함되는 경우 인덱스를 초과하는 에러를 회피하기 위해 아무 카드도 포함되지 않는 그룹이 항상 하나씩 있다고 가정하여 문제를 해결하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <vector>
#include <algorithm>

using namespace std;

void Partition(vector<vector<int>>& partition, const vector<int>& cards, vector<int>& used, int start)
{
    if (used[cards[start] - 1])
        return;
    
    partition.push_back(vector<int>());
    vector<int>& p = partition.back();
    while (!used[cards[start] - 1])
    {
        p.push_back(cards[start]);
        used[cards[start] - 1] = true;
        start = cards[start] - 1;
    }
}

int solution(vector<int> cards)
{
    int n = cards.size();
    vector<int> used(n);
    vector<vector<int>> partition(1);
    
    for (int i = 0; i < n; i++)
        Partition(partition, cards, used, i);
    
    sort(partition.begin(),
         partition.end(),
         [](const vector<int>& a, const vector<int>& b)
         {
             return a.size() > b.size();
         });
    
    return partition[0].size() * partition[1].size();
}

 

실행 결과