Lv2. 혼자 놀기의 달인

 

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

프로그래머스

 

 

while 문을 활용한 DFS로 풀이하였다.

이번 문제는 cards[] 배열이 주워질 때, 랜덤으로 어떠한 두 박스를 고른다.

두박스 안에는 박스번호와 박스안의 카드번호가 주워지는데 카드번호를 통해 

다음박스 를 열게되고 그 박스안의 카드번호에 해당하는 박스를 다시 여는

반복을 통해 cycle을 측정한 다음

2가지 cycle의 크기 가 최대가 될 수 있는

값을 구하는 문제다.

 

우선 boolean[] isVisited 를 활용하여 방문체크를 해주고

반복문 for 를 통해 1번박스부터 모든 박스를 연다.

count와 current(박스번호는 index+1 이기에) 변수를 통해

cycle의 크기와 다음박스 번호를 저장하면서

 

current와 처음 시작한 i 번 박스 즉 current == i가 되면 count 를

ArrayList<>에 담는다.

 

Collections.sort를 활용하여 내림차순 정렬 한 다음

get() 함수를 통해 최댓값을 계산해주되

list size가 2 이하라면 0 을 반환해주었다.

 

 

 

import java.util.*;

class Solution {
    
    ArrayList<Integer> list = new ArrayList<>();
    boolean[] isVisited;
    
    public int solution(int[] cards) {
        int size = cards.length;
        isVisited = new boolean[size];
        for(int i = 0 ; i < size ; i++){
            if(!isVisited[i])
            {
                int current = i;
                int count = 0;
                
                while(!isVisited[current]){
                    isVisited[current] = true;
                    count++;
                    current = cards[current]-1;
                }
                
                if(current == i){
                    list.add(count);
                }
            }
        }
        Collections.sort(list,(o1,o2)-> o2 - o1);
        if(list.size() < 2)        return 0;
        return list.get(0)*list.get(1);
    }
}