[프로그래머스 2레벨] 혼자 놀기의 달인 (C++)

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

using namespace std;

int visited[101];

int solution(vector<int> cards) {
    int answer = 0;
    
    vector<int>v;
    for(int i=0; i<cards.size(); i++)
    {
        int cur = cards[i];
        int cnt = 0;
        
        while(!visited[cur]) //그룹 찾기
        {
            visited[cur] = 1;
            cur = cards[cur-1]; //번호에 해당하는 카드 오픈
            cnt++; //그룹의 갯수 추가
        }
        if(cnt) v.push_back(cnt);
    }
    
    sort(v.begin(), v.end(), greater<int>());
    if(v.size()>=2)answer = v[0]*v[1];
    
    return answer;
}

 

문제가 다소 복잡해보이지만, 보이는 그대로 구현해주면 되는 문제이다.

그룹을 찾아야 하므로, 현재 고른 카드가 중복이 나올때 까지 반복하여 카드를 오픈하며 그룹에 개수를 카운팅해준다.

문제에 주어진 조건에 따라, 다음 오픈 카드는 현재 번호에 해당하는 카드를 오픈하며 개수를 카운팅하고 다시 방문하는 경우가 나올때까지 반복한다.

 

이렇게 추가된 카운트는 해당 그룹의 총 개수이다.

따라서 이를 반복하면 가능한 그룹에 대한 각 개수들을 알 수 있다.

가장 큰 값을 얻어야 하므로, 해당 카운트 값을 담은 벡터를 내림차순해서 처음 2개의 값을 곱해주면 된다.