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

 

불과 며칠 전에 문제를 읽다가 이해가 안되어서 끝까지 읽지도 못하고 즈레 겁먹어 그만뒀던 문제다.

마치 보드게임장에 가서 설명을 잘 이해하느냐의 차이인 것 같다.

책을 읽는 것도 도움이 많이 되는 듯 하다.

 

집중력이 필요하고, 겁먹지 않는 점이 중요하다.

이 문제는 쓸데없는 얘기가 주구장창 이어지다가, 결국 출력예시만 봐도 문제를 풀 수 있다.

 

 

문제 정리

그냥 group화 dfs 문제이다.

그룹이 하나밖에 없으면 0을 리턴하면 되고

그룹이 두 개 이상이라면, 그룹 인원이 가장 많은 두 그룹을 곱해 주기만 하면 된다.

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

using namespace std;

int group[101];
int groupCounter = 0;

void dfs(vector<int>& cards, int index, int groupId) {
    
    groupCounter++;
    group[index] = groupId;
    
    if(group[cards[index] - 1] == 0) {
        dfs(cards, cards[index] - 1, groupId);
    }
}

int solution(vector<int> cards) {
    
    int groupId = 0;
    
    vector<int> groupList;
    
    for(int i = 0; i < cards.size(); i++) {
        
        if(group[i] == 0) {
            groupCounter = 0;
            dfs(cards, i, ++groupId);
            groupList.push_back(groupCounter);
        }
        
    }
    
    sort(groupList.begin(), groupList.end(), greater<int>());
    
    if(groupId == 1)
        return 0;
    else
        return groupList[0] * groupList[1];
    
}