프로그래머스 혼자 놀기의 달인 [Lv. 2] (C++)

프로그래머스

 

범희는 카드 게임을 하나 만들었습니다. 100장 이하의 중복되지 않는 숫자가 적힌 카드를 준비하고, 준비된 카드들을 각각의 상자에 하나씩 넣고 섞은 후 나열해 놓으면 게임을 시작할 수 있습니다. 

게임 방법

1. 임의의 상자를 하나 선택합니다. 

2. 상자 안의 숫자를 확인하고, 해당 수에 위치한 상자를 열어줍니다.

3. 더 이상 오픈할 상자가 없을 때 까지 2번을 반복해주고 오픈한 상자의 개수를 기록합니다.

4. 임의의 상자는 총 2번 선택 할 수 있으며, 각각의 상자를 오픈하면서 기록한 개수를 곱한 값이 게임의 점수입니다.

이때, 게임에서 얻을 수 있는 최고 점수가 몇점인지 찾아주세요

 

 

풀이 방법

"중복되지 않는 카드"라는 조건이 있기 때문에 모든 상자는 진입 차수가 1개 입니다.

즉, 각각의 상자는 하나의 그룹에만 속해있으며, 오픈 하는 상자의 경우의 수와는 상관 없이 그룹은 이미 정해져 있다는 걸 알 수 있습니다.

 

그렇기 때문에 우선적으로 그룹을 찾아줘야합니다. 저는 방문 배열을 이용했습니다.

vector<bool> visited(cards.size(), false);

그룹을 찾기 위해 상자를 열 때, 오픈되지 않은 상자라면 상자 그룹을 업데이트 해주고,

오픈된 상자라면 한 바퀴를 돌았다는 것으로 판단하여 탐색을 종료합니다.

 

이후, 가장 큰 그룹 두 개를 곱하여 반환하는 것으로 문제를 마무리할 수 있겠습니다.

 

정답 코드

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

using namespace std;

int solution(vector<int> cards) {

    vector<bool> visited(cards.size(), false);
    
    vector<int> answer = {0};
    for (int i = 0 ; i < cards.size(); i++)
    {
        if (visited[i])
            continue;
        visited[i] = true;
        
        int size = 1;
        int idx = cards[i]-1;
        while(visited[idx] == false)
        {
            visited[idx] = true;
            idx = cards[idx]-1;
            size++;            
        }
        
        answer.push_back(size);
    }
    
    sort(answer.begin(), answer.end(), [](int A, int B){return A > B;});
    return answer[0] * answer[1];
}

answer = {0}을 해준 이유는 그룹이 하나만 있을 때, 0을 반환하기 위함입니다.