[자바] 혼자 놀기의 달인

문제

풀이

문제 내용이 긴데 요점만 말하면

박스를 점으로 하는 그래프가 있고, 그 그래프의 사이클 길이가 가장 큰 두개를 찾아서 곱하라는 이야기다.

즉, 사이클을 어떻게 해서 찾을지만 생각하면 쉽게 풀 수 있는 문제다.

나는 카드숫자와 방문여부를 저장하는 박스 객체를 만들고 방문한 적 없는 박스라면 다음 박스를 찾아가는 방식으로 사이클을 찾는것을 구현했다.

import java.util.*;

class Solution {

    public int solution(int[] cards) {
        //박스 객체를 보관할 배열 생성
        Box[] boxArray = new Box[cards.length];
        List<Integer> cycle = new ArrayList<>();
        
        //박스 객체를 카드 숫자만큼 생성
        for(int i = 0 ; i<cards.length; i++){
            boxArray[i] = new Box(cards[i]);
        }
        
        //박스 객체들의 사이클을 찾아 사이클 리스트에 정리
        for(int j = 0; j<boxArray.length; j++){
            if(!boxArray[j].visited){
                cycle.add(checkCycle(j,boxArray,0));
            }
        }
        
        //리스트를 정렬하여 가장 큰 사이클 두개의 길이를 곱한 값을 리턴, 단 사이클이 하나일땐 0을 리턴
        return cycle.size() > 1 ? cycle.stream().sorted((a,b)->b-a).limit(2).reduce((a,c)->a*c).get() : 0;
        
    }
    
    //사이클을 찾아 길이를 반환하는 함수
    public int checkCycle(int i, Box[] boxArray,int count){
        if(boxArray[i].visited) {
            return count;
        }else{
            boxArray[i].visit();
            return checkCycle(boxArray[i].boxCard-1,boxArray,count+1);
        }

    }
    
    //박스 객체
    public class Box {
        //박스에 들어있는 카드
        private int boxCard;
        //박스의 방문 여부
        private boolean visited = false;

        public Box(int boxCard){
            this.boxCard = boxCard;
        }
        
        //박스에 방문
        public void visit(){
            this.visited = true;
        }

    }

}

찾아낸 사이클 길이는 cycle 리스트에 저장하여 마지막에 내림차순으로 정렬한 리스트의 앞 두개 요소만을 곱해 리턴하는 것으로 답을 찾아냈다.

이 때, 박스의 사이클이 1개 이하일 때는 0을 리턴하도록 삼항연산자를 사용했다.