문제 출처

1. 문제설명

  • 최대 100장의 카드 번호 리스트가 주어진다.
  • 게임 방법
    • 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드 확인
    • 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자 확인
    • 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복
    • 이렇게 연 상자들은 1번 상자 그룹
  • 게임의 점수 출력
    • 1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값


2. 입/출력

  • 2 <= cards <= 100
    • 자연수 원소
    • 중복되는 원소 없음.


3. 문제 분류

  • Simulation


4. 알고리즘 설계

  • [8,6,3,7,2,5,1,4]를 통한 문제 이해
    • 1번 상자
      • 처음에는 1번째 원소인 8을 뽑는다.
      • 이후 8번째 원소에 해당하는 4를 뽑는다.
      • 이후 4번째 원소에 해당하는 7을 뽑는다.
      • 이후 7번째 원소에 해당하는 1을 뽑는다.
      • 이후 1번째 원소에 해당하는 8을 뽑으려 했으나 이미 방문한 상태이다.
      • 1번 상자 그룹은 {8, 4, 7, 1}로 총 4개의 원소이다.
    • 2번 상자
      • 1번째 원소는 방문했으므로 건너뛴다.
      • 2번째 원소인 6을 뽑는다.
      • 6번째 원소인 5를 뽑는다.
      • …..
  • 위와 같은 방식으로 상자의 개수가 계산된다.
  • 상자의 개수가 큰 순으로 정렬하고 0번째, 1번째 상자의 개수를 곱한 값을 출력하면 되는 문제였다.
    • 상자의 개수가 2개보다 작으면 점수를 얻을 수 없어 0을 리턴하면 된다.


5. 전체 코드

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> cards) {
    int sz = cards.size();
    vector<bool> vis(sz+1, false);
    vector<int> res;
    
    for(int& cur : cards) {
        int cnt = 0;
        
        while(!vis[cur]) {
            vis[cur] = true;
            cur = cards[cur-1];
            cnt++;
        }
        
        if(cnt > 0) res.push_back(cnt);
    }
    
    if(res.size() <= 1) return 0;
    else {
        sort(res.begin(), res.end(), greater<>());
        return res[0] * res[1];
    }
}


6. 소감