이 문제는 상자 안에 있는 숫자 카드를 따라가며 그룹을 형성하고, 그 중 두 개의 가장 큰 그룹 크기를 곱해 최대 점수를 계산하는 문제이며 그래프 탐색과 유사한 방식으로 해결할 수 있다.
카드는 각 상자에 적힌 숫자에 따라 다음 상자를 가리키며, 이 연결 관계는 사이클을 형성하고 탐색은 방문 여부를 기록하여 이미 탐색한 상자를 다시 방문하지 않도록 하며, 이를 통해 그룹을 효율적으로 찾을 수 있다. DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 사용해 그룹의 크기를 계산할 수 있다. 탐색이 끝난 뒤에는 모든 그룹 크기를 내림차순으로 정렬한 후, 문제에서 제시한 가장 높은 점수를 구하기 위해서는 가장 큰 두 그룹 크기를 곱하여 점수를 계산한다. 이 과정에서 모든 상자는 한 번만 방문하므로 시간 복잡도는 상자의 수 N에 비례하며, 그룹 크기를 정렬하는 데 추가적인 비용이 발생한다.
예를 들어, 카드 배열이 [8, 6, 3, 7, 2, 5, 1, 4]라면, 첫 번째 그룹은 [1 → 8 → 4 → 7 → 1]로 크기가 4이고, 두 번째 그룹은 [2 → 6 → 5 → 2]로 크기가 3입니다. 따라서 최대 점수는 4×3=12가 된다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class TheMasterOfSoloFun {
public int solution(int[] cards) {
List<Integer> group = new ArrayList<>();
boolean[] visited = new boolean[cards.length];
for (int i = 0; i < cards.length; i++) {
if (!visited[i]) {
int count = 0;
int index = i;
while (!visited[index]) {
visited[index] = true;
index = cards[index] - 1;
count++;
}
if (count > 0) group.add(count);
}
}
group.sort(Collections.reverseOrder());
if (group.size() < 2) return 0;
return group.get(0) * group.get(1);
}
}