[programmers] 혼자 놀기의 달인

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

방문한 상자를 visited[]로 표시.

1~n까지 루프를 돌면서,

!visited[]인 상자에 대해서만 상자를 열어 작업을 시작한다.

열어본 상자의 개수를 그룹의 개수로 저장 + priority queue에 각 그룹의 개수를 저장.

그룹의 개수 중 큰 두 개를 선택해 곱해 리턴.

 

---------------------------------------------------풀이----------------------------------------------------

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

// 그룹의 카드 개수 내림차순.
priority_queue<int, vector<int>, less<int> > pq;
bool visited[101] = {false, };
vector<int> cards;

int find_group(int cur){
    if(visited[cur]){
        return 0;
    }
    visited[cur] = true;
    return find_group(cards[cur-1])+1;
}

// 카드 1~100. n 이하의 카드와 그 수만큼의 상자.
// 카드를 무작위로 섞어 상자에 1~n을 붙임.
// 임의의 상자를 선택해 카드 확인->그 카드 숫자의 상자 열어 카드 확인->...
// => 1번 상자 그룹
// 임의의 상자를 선택해 카드 확인->그 카드 숫자의 상자 열어 카드 확인->...
// => 2번 상자 그룹
// 게임 점수 = 1번 상자 수 * 2번 상자 수
// 최대 점수=?
// 상자 순서대로 카드 번호 배열 cards.
int solution(vector<int> _cards) {
    cards = _cards;
    int answer = 0;
    // 그룹 별 개수 구하기
    for(int i = 1; i <= cards.size(); i++){
        if(!visited[i]){
            pq.push(find_group(i));
        }
    }
    
    int n1 = pq.top(), n2 = 0;
    pq.pop();
    // 그룹이 하나만 존재하면 0점
    if(!pq.empty()){
        n2 = pq.top();
    }
    answer = n1 * n2;
    
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

cards[]는 0부터 나타나있는데 실제로 카드의 숫자는 1부터이므로 이 부분에서 오류가 났었다.