혼자 놀기의 달인(21분)

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

구현 아이디어 5분 구현 16분

풀이

1. check[i]가 0이면 아직 i번째 상자는 그룹이 없다.
2. while문을 돌며 i 위치에 있는 카드를 확인하는데 check[idx_pick]이 0이 아니라면 사이클이 생겼다는 뜻이다.

• group 값을 1 더하고 i를 0 초기화한다.

3. for문이 끝나면 check 배열은 각자의 group 값으로 바뀌어있다.

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

using namespace std;

int check[101];

int solution(vector<int> cards) {
    int answer = 0;
    
    vector<int> tmp(cards.size() + 1);
    for(int i = 1; i <= cards.size(); ++i) tmp[i] = cards[i - 1];
    
    int group = 1;
    for(int i = 1; i <= cards.size(); ++i)
    {
        if(check[i] == 0)
        {
            check[i] = group;
            while(true)
            {
                // 처음 8 나올 것.
                int idx_pick = tmp[i];
                
                if(check[idx_pick])
                {
                    i = 0;
                    ++group;
                    break;
                }
                
                check[idx_pick] = group;
                i = idx_pick;
            }
        }
    }
    
    // 디버깅.
    //for(int i = 1; i <= cards.size(); ++i)
        //printf("%d ", check[i]);
    
    vector<int> result(cards.size() + 1);
    for(int i = 1; i <= cards.size(); ++i)
    {
        int idx_group = check[i];
        ++result[idx_group];
    }
    
    sort(result.begin(), result.end(), greater());
    
    return answer = result[0] * result[1];
}