[프로그래머스] 혼자 놀기의 달인

문제

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=java 

프로그래머스

접근 방법 및 풀이

배열의 값은 다음 수의 인덱스를 가리키고 있음

가리킨 인덱스를 추적하여 시작한 인덱스로 되돌아오면 하나의 묶음

각각의 묶음의 길이 중 가장 긴 길이와 두 번째 긴 길이의 곱을 반환

묶음의 길이를 구하기 위하여 재귀를 사용

 

public class Q30_131130 {
    public int solution(int[] cards) {
        int length = cards.length;

        int[] max = {-1, -1};

        for (int i = 0; i < length; i++) {
            if (cards[i] == -1) {
                continue;
            }

            int circleSize = circuit(cards, i);

            if (max[0] < circleSize) {
                max[1] = max[0];
                max[0] = circleSize;
            } else if (max[1] < circleSize) {
                max[1] = circleSize;
            }

        }

        if (max[0] == length) {
            return 0;
        } else {
            return max[0] * max[1];
        }
    }

    private int circuit(int[] cards, int index) {
        if (cards[index] == -1) {
            return 0;
        }

        int nextIndex = cards[index] - 1;
        cards[index] = -1;

        return circuit(cards, nextIndex) + 1;
    }
}