[프로그래머스] Level 2. 혼자 놀기의 달인

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

프로그래머스

 

1. 모든 카드를 돌면서 상자번호를 매긴다. 
2. 만약 상자번호가 이미 0이 아니라면 할당이 끝난것이므로 break
3. 상자번호 갱신이 가능하다면 갱신한뒤 index를  다음검사 인덱스로 설정한다.
4. 이 작업을 완료했을 때, counts 배열의 개수는 총 박스의 수가 되고, counts[i] 의 요소는 i+1번 상자그룹의 개수가 된다. 
5. 만약 counts배열의 개수가 1이라면, 상자가 1개밖에 나오지 않았다는 의미이므로 0을 리턴한다.
6. counts 배열 안에서 가장 큰 두 수를 곱해서 리턴한다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> cards) {
    int answer = 0;
    
    vector<int> groups(cards.size(), 0);
    vector<int> counts;
    int num = 1;
    for(int i=0; i<cards.size(); i++){    
        int index = i;
        bool flag = false;
        
        while(groups[index]==0){
            
            flag = true;
            groups[index] = num;
            
            if(counts.size() < num) counts.push_back(0);
            counts[num-1] ++;
            
            index = cards[index]-1;
        }

        if(flag) num++;
    }
    
    if(counts.size() <=1) return 0;
    sort(counts.rbegin(), counts.rend());
    
    return counts[0]*counts[1];
}