문제 - 혼자 놀기의 달인

문제 설명

해당 글을 읽는데 제대로 이해를 못하고 처음에는 순열로 상자안에 들어있는 카드 번호를 만들어서 문제를 풀었다. 이 문제는 처음부터 카드 번호를 순서대로 담긴 배열을 주기 때문에 경로탐색느낌으로 문제를 풀면 된다.

문제 접근

1. 우선순위 큐를 내림차순으로 정렬을 한다. 제일 높은 숫자의 1,2번 숫자를 가져오기 위함
2. dfs를 이용하여 상자를 하나씩 열어본다.
3. 이미 열려진 상자를 오픈할려고 하면 현재까지 오픈한 상자의 개수를 우선순위 큐에 저장한다.
4. pq의 사이즈가 1인 경우에는 1번 그룹의 상자들을 만들고 남은 상자의 갯수가 없다는 의미로 0점을 출력해준다
5. 우선순위 큐의 1,2번을 추출하여 곱한다.

import java.util.*;

class Solution {
    PriorityQueue<Integer> pq;
    public int solution(int[] cards) 
    {
        int answer = 0;
        int len = cards.length;
        boolean visited[] = new boolean[len];
        pq = new PriorityQueue<>(Collections.reverseOrder());
        for(int i =0;i<len;i++)
        {
            if(!visited[i])
            {
                process(i,cards,visited,0);
            }
        }
        //1번 상자의 그룹만 있는 경우
        if(pq.size() < 2)
        {
            return 0;
        }
        
        int first = pq.poll();
        int second = pq.poll();
        return first * second;
    }
    
    public void process(int num,int []cards,boolean []visited,int cnt)
    {
        //이미 열려진 상자라면
        if(visited[num])
        {
            pq.add(cnt);
            return;
        }
        
        visited[num] = true;
        process(cards[num]-1,cards,visited,cnt+1);
        
    }
    
}