문제 풀이(2)

https://school.programmers.co.kr/learn/courses/30/lessons/131130

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

class Solution {

	static int[] parent ;

	static boolean[] visited;
	public static void main(String[] args) {
		solution(new int[]{8,6,3,7,2,5,1,4});
	}

    public static int solution(int[] cards) {
        int answer = 0;

		parent = new int[cards.length + 1];

		int idx = 1;

		for (int i = 0; i < cards.length; i++) {
			parent[idx++] = cards[i];
		}

		visited = new boolean[cards.length + 1];

		
		
		for (int i = 1; i < parent.length; i++) {

			if (visited[i]) {
				continue;
			}
			
			union(i, parent[i]);

		
			parent[i] =  i;

		
			
		}


		HashMap<Integer, Integer>map = new HashMap<>();

		for (int i = 0; i < parent.length; i++) {
			
		
			map.putIfAbsent(parent[i], 0);

			map.put(parent[i], map.get(parent[i]) + 1);
		}

		

	

		ArrayList<Integer>list = new ArrayList<>(map.values());

		Collections.sort(list , Collections.reverseOrder());


        if(list.get(0) > 1 && list.get(1) == 1)return 0;

        return list.get(0) * list.get(1);
    }


	public static void union(int a , int b)
	{

		if (a == b) {
			return;
		}
		

		if (a != b) {

			int temp = parent[b];

			

			parent[b] = a;

			visited[b] = true;

			

			union(parent[b], temp);
		}
	}
}

배열 parent에는 각 카드가 속한 집합의 대표값이 저장되고, visited 배열은 해당 인덱스의 카드를 이미 처리했는지 여부를 나타낸다.union 함수는 두 카드를 묶을 수 있도록 묶어주는 함수입니다. 재귀적으로 부모를 찾아가며 두 카드를 같은 집합으로 묶는다.배열 parent를 이용하여 각 카드가 속한 집합의 크기를 카운트한다. 이를 위해 HashMap인 map을 사용하고, map의 key에는 카드가 속한 집합의 대표값이 저장되고, value에는 해당 집합의 크기가 저장된다.map의 value 값들을 내림차순으로 정렬한 뒤, 첫 번째와 두 번째 값의 곱을 결과로 반환한다.