프로그래머스 혼자 놀기의 달인 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];
    
}

 

 

---

다시 풀었다.

똑같이 풀었네.. 신기하다. 감이 죽지 않았다는거겠지!

#include <string>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

// 그룹화 DFS
// [8,6,3,7,2,5,1,4]

int groupScore;
int groupCounter;
int group[101];


void dfs(int start, int groupNumber, vector<int>& cards) {
    
    group[start] = groupNumber;
    groupScore++;
    
    if(group[cards[start] - 1] == -1) {
        dfs(cards[start] - 1, groupNumber, cards);
    }
}

int solution(vector<int> cards) {
    int N = cards.size();
    memset(group, -1, sizeof(group));
    
    priority_queue<int, vector<int>, less<int>> pq;
    
    for(int i = 0; i < N; i++) {
        if(group[i] == -1) {
            groupScore = 0;
            dfs(i, ++groupCounter, cards);
            pq.push(groupScore);
        }
    }
    
    int first = pq.top();
    pq.pop();
    int second = pq.top();
        
    return groupCounter == 1 ? 0 : first * second;
}