프로그래머스 - 혼자 놀기의 달인(Java)

파인드(find) 문제입니다.

 

문제를 요약하면 '같은 집합을 이루는 배열의 원소 개수를 찾아 가장 큰 두 개를 곱하라' 입니다.

입력의 각 원소는 자신과 같은 집합을 이루는 위치를 가르키고 있습니다.

즉, 이미 유니온(union)이 되어있는 집합이 입력으로 주어지는 것입니다.

각 위치에서 find연산을 통해 어느 집합에 속하는지 파악하면 끝나는 문제입니다.

단, 주의해햐할 점이 있습니다.

입력으로 주어지는 배열은 순환을 발생시킬 수 있기 때문에 이미 방문한 곳은 재방문하지 않도록 하면 됩니다.

find 연산을 할 때, 최상위 부모를 저장시켜 방문한 곳은 값을 확인하면 됩니다.

 

[구현 코드]

import java.util.*;

class Solution {
    int[] parents;

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

        parents = cards;
        int n = cards.length;

        Map<Integer, Integer> counts = new HashMap<>();

        for(int i=0; i<n; i++){
            parents[i]--;
        }

        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++){
            int num = 0;
            if(!visited[i]){
                num = find(i, visited);
            }else{
                num = parents[i];
            }

            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        if(counts.size() < 2){
            answer = 0;
        }else{
            List<Integer> vals = new ArrayList<>();
            for(int v : counts.values()){
                vals.add(v);
            }

            vals.sort((o1, o2) -> o2-o1);

            answer = (vals.get(0) * vals.get(1));
        }

        return answer;
    }


    int find(int a, boolean[] visited){
        if(a == parents[a] || visited[a]){
            return a;
        }
        visited[a] = true;
        
        // find연산을 하되, 최상위 부모를 저장하도록 함
        return parents[a] = find(parents[a], visited);
    }
}