lv2) 혼자 놀기의 달인

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

프로그래머스

 

#include <string>
#include <vector>
#include<queue>
#include<iostream>
//union find로 해도될것 같은데 복잡할거 같아서
// DAT로 진행 가능, 우선순위 힙에 카운팅 진행하기.  with visited


using namespace std;
int visited[101];
int solution(vector<int> cards) {
    priority_queue<int>pq; // 우선순위 힙정렬 통해 O(NlogN) 시간복잡도로 그룹들의 원소 갯수 를 정렬
    int groupCnt = 0; // 용도 1번 상자 그룹 제외하고 남는 상자 없으면 그대로 게임 종료 하기 위해 카운팅하는 목적
    for(int y = 0; y < cards.size(); ++y){
        int c = cards[y];
        int cnt = 0;
        if(visited[y+1] != 0) continue; // 이미 진행된 원소이면 그룹이 존재하기에 진행 할 필요 없다.
        groupCnt++;
        visited[y+1] = 1;
        cnt = 1;
        while(visited[c]==0){ // 하나의 그룹에 원소 만들며, 해당 원소의 갯수 cnt로 카운팅
            cnt++;
            visited[c] = 1;
            c = cards[c-1];
        }
        pq.push(cnt);
    }
    if(groupCnt == 1) return 0; // 그룹이 하나밖에 없을 경우
    int a = pq.top();
    pq.pop();
    int b = pq.top();
    return answer = a * b; // 그룹들 간 최대 원소 갯수를 가진 두 그룹 선택해서 곱함 
}