프로그래머스 - 혼자 놀기의 달인 [C++]

이 문제는 구현 문제이다.

 

문제 설명 자체가 좀 어려운데, 간단하게 말하면 해당 위치의 배열 값으로 위치를 계속 바꿔가면서, 순환되는 숫자들을 그룹으로 묶고, 그 그룹들 중 가진 숫자가 큰 두개의 그룹의 숫자를 곱한 값을 리턴하면 된다.

 

기본으로 주어지는 cards는 인덱스가 0부터 시작해 문제가 복잡해질 것 같아 새로 card 배열을 만들고 인덱스와 카드 숫자가 일치하도록 만들었다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX 100

int card[MAX + 1];
int maxSize;

void init(vector<int>& cards) {
    for (int i = 0; i < cards.size(); i++) {
        card[i + 1] = cards[i];
    }
}

int makeGroup(vector<bool>& isGrouped, int start) {
    int present = start;
    int result = 0;
    
    while (!isGrouped[present]) {
        result++;
        isGrouped[present] = true;
        int next = card[present];
        present = next;
    }
    
    return result;
}

vector<int> makeGroupList() {
    vector<int> results;
    vector<bool> isGrouped(maxSize + 1, false);
    
    for (int i = 1; i <= maxSize; i++) {
        if (!isGrouped[i]) {
            int temp = makeGroup(isGrouped, i);
            
            results.push_back(temp);
        }
    }
    
    return results;
}

int solution(vector<int> cards) {
    int answer = 0;
    
    maxSize = cards.size();
    init(cards);
    
    vector<int> results = makeGroupList();
    
    sort(results.begin(), results.end(), greater<int>());
    
    if (results.size() == 1) {
        return 0;
    }
    
    answer = results[0] * results[1];
    
    return answer;
}