혼자 놀기의 달인(자바, 프로그래머스)

풀이 아이디어

• Union Find

문제 이해를 처음에 잘못 해서 매우 헷갈렸다.
간단하게 해석하자면, n 개의 노드가 각자 하나의 노드를 가리키는데, 이때 모든 노드가 서로 다른 하나의 가리켜진다 (모든 노드가 Indegree, Outdegree 가 1인 상태). 그리고 이어진 노드들 끼리 그룹을 형성할 때 "1개의 그룹으로 모든 노드가 연결되면 0점, 아니라면 1번째 2번째 큰 그룹의 노드 개수를 곱한 것이 점수" 이다.

import java.util.*;

class Solution {
    
    static int[] parents;
    static boolean[] visited;
    
    public int solution(int[] cards) {
        int answer = 1;
        int len = cards.length;
        parents = new int[len+1];
        visited = new boolean[len];
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < len; i++){
            list.add(i);
            parents[i+1] = i+1;
        }
        while(!list.isEmpty()){
            Integer i = list.remove(0);
            while(true){
                if(!visited[i]){
                    visited[i] = true;
                    int next = cards[i];
                    union(i+1, next);
                    i = next - 1;
                    list.remove(i);
                }else{
                    break;
                }
            }
        }
        
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 1; i < len+1; i++){
            int group = find(i);
            if(group == -1){
                map.put(i+1, map.getOrDefault(i+1,0)+1);
            }else{
                map.put(group, map.getOrDefault(group,0)+1);
            }
        }
        System.out.println(Arrays.toString(parents));
        if(map.size() == 1) return 0;
        ArrayList<Integer> arr = new ArrayList<>(); // 그룹의 크기가 큰 1,2 번 그룹을 구하기 위해 정렬할 수 있는 list 에 담기
        for(Integer key : map.keySet()){
            int cnt = map.get(key);
            // System.out.println("key: "+key+" cnt: "+cnt);
            arr.add(cnt);
        }
        Collections.sort(arr, (Integer a, Integer b) -> {return b - a;});
        answer = arr.get(0) * arr.get(1);
        return answer;
    }
    
//     자식이 부모를 찾을 때 까지 갱신
    public int find(int x) {
        if(parents[x] == x) return x;
        return find(parents[x]);
    }
    
//     두 요소의 부모가 같도록 갱신
    public boolean union(int x, int y) {
        x = find(x); //x의 부모노드 찾기
        y = find(y); //y의 부모노드 찾기

        // 이미 같은 그래프에 속해있을 때 false 반환
        if(x == y) return false;

        if(x <= y) parents[y] = x;
        else parents[x] = y;
        return true;
    }
}