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

문제 링크

제출 코드(통과)

using System;

public class Solution {
    public int solution(int[] cards)
    {
        var opened = new bool[cards.Length];
        var max1 = 0;
        var max2 = 0;
        for (var i = 0; i < cards.Length; i++)
        {
            if (opened[i]) continue;
            opened[i] = true;
            var j = cards[i] - 1;
            var count = 1;
            while (!opened[j])
            {
                opened[j] = true;
                j = cards[j] - 1;
                count++;
            }

            if (count > max1)
            {
                max2 = max1;
                max1 = count;
            }
            else if (count > max2)
            {
                max2 = count;
            }
        }
        return max1 * max2;
    }
}

카드에 중복이 없기 때문에, 상자 관계를 그래프로 그리면 모든 상자가 루프를 만든다. (연결된 그래프의 일부만 루프에 갇히는 경우가 존재할 수 없음. 그러기 위해선 한 상자를 가리키는 상자가 여러 개여야 하기 때문) 따라서 이미 열려있는 상자가 속한 경로의 길이는 루프의 길이로 고정되어 변하지 않기 때문에 다시 볼 필요가 없다. 루프의 길이를 재면서 가장 긴 두 개만 남긴다. 만약 루프가 하나면 max2가 0으로 남기 때문에 자연스럽게 0을 반환하게 된다.

내부 루프 진입을 좀 더 깔끔하게 수정(로직엔 차이 없음)

using System;

public class Solution {
    public int solution(int[] cards)
    {
        var opened = new bool[cards.Length];
        var max1 = 0;
        var max2 = 0;
        for (var i = 0; i < cards.Length; i++)
        {
            if (opened[i]) continue;
            var j = i;
            var count = 0;
            while (!opened[j])
            {
                opened[j] = true;
                j = cards[j] - 1;
                count++;
            }

            if (count > max1)
            {
                max2 = max1;
                max1 = count;
            }
            else if (count > max2)
            {
                max2 = count;
            }
        }
        return max1 * max2;
    }
}