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

혼자 놀기의 달인

문제 링크

혼자 놀기의 달인

분석

카드는 총 100장으로, 각 카드는 1부터 100까지의 숫자가 적혀있습니다.
2 이상 100이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비합니다.

준비된 상자에 카드를 한장씩 넣고 상자를 무작위로 섞어 일렬로 나열합니다.
상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호룰 붙입니다.

임의의 상자를 열면 안에 있는 숫자를 확인하고 해당하는 번호의 상자를 다음에 엽니다.
이 과정을 반복하며, 열어야 하는 상자가 열려있을 때까지 반복합니다.
즉, 이미 연 상자는 다시 열 수 없으며 반복이 끝나는 조건이 됩니다.

반복 중 열었던 상자들이 하나의 그룹이 됩니다.
이렇게 생성된 그룹들 중 크기를 곱한 값이 점수가 되는데, 두 개의 그룹의 크기를 곱했을 때 만들 수 있는 가장 큰 최대 점수를 구해 반환해야합니다.

DFS알고리즘으로 그래프의 사이클 탐색을 해주어 풀이할 수 있습니다.
이미 방문한 상자는 다시 열 수 없으므로, 배열을 사용해 방문 상태를 관리합니다.
각 사이클(그룹)의 크기를 저장한 후, 서로 다른 두 사이클 중 가장 큰 두개를 선택하여 곱합니다.
만약, 사이클이 하나뿐이라면 점수는 0입니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> cards) {
    int answer = 0;
    
    // 상자들의 개수
    int n = cards.size();
    
    // 상자들의 방문 여부 저장
    vector<bool> visited(n, false);
    
    // 각 그룹의 크기를 저장
    vector<int> groupSizes;
    
    // 모든 상자에 대해서 순회
    for (int i = 0; i < n; ++i)
    {
        // 이미 방문한 상자인 경우 건너뛴다.
        if (visited[i])
        {
            continue;
        }
        
        // 현재 상자의 인덱스
        int current = i;
        // 현재 상자의 인덱스로 시작한 그룹의 크기
        int count = 0;
        
        // 방문하지 않은 상자를 따라가며 사이클을 탐색
        while (!visited[current])
        {
            // 방문 처리
            visited[current] = true;
            // 카드에 적힌 숫자로 다음 상자의 인덱스를 구한다.
            current = cards[current] - 1;
            // 그룹 크기 증가
            ++count;
        }
        
        // 구한 그룹의 크기 저장
        groupSizes.push_back(count);
    }
    
    // 그룹의 개수가 2개 이상인 경우 내림차순으로 정렬하고, 가장 큰 값 2개를 곱한다.
    if (groupSizes.size() >= 2)
    {
        sort(groupSizes.begin(), groupSizes.end(), greater<int>());
        answer = groupSizes[0] * groupSizes[1];
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 상자의 개수만큼 순회하는 반복문 $O(n)$
• 각 상자로 시작하는 사이클 탐색 $O(n)$
  • 방문을 처리하기 때문에 상자의 개수만큼 순회하는 반복문과 $O(n^2)$이 되지 않습니다.
• 그룹 정렬 $O(n \ log \ n)$
• $O(n) + O(n \ log \ n)$

공간 복잡도는 $O(n)$입니다.

• 상자들의 방문 여부를 저장하는 vector<bool> visited $O(n)$
• 각 그룹의 크기를 저장하는 vector<int> groupSizes $O(n)$
• $O(n) + O(n)$

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.16MB)
테스트 3 〉 통과 (0.01ms, 3.64MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 3.59MB)
테스트 7 〉 통과 (0.01ms, 4.45MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.01ms, 4.22MB)
테스트 10 〉 통과 (0.01ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 3.69MB)
테스트 12 〉 통과 (0.01ms, 4.14MB)
테스트 13 〉 통과 (0.01ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 3.68MB)
테스트 15 〉 통과 (0.01ms, 4.21MB)