양말 상인 코드 챌린지 해결

John은 옷가게에서 일합니다. 그는 판매를 위해 색깔별로 짝을 지어야 하는 큰 양말 더미를 가지고 있습니다. 각 양말의 색상을 나타내는 정수 배열이 주어지면 색상이 일치하는 양말이 몇 켤레가 있는지 확인하십시오.

예를 들어, 색상이 ar = [1, 2, 1, 2, 1, 3, 2]인 n = 7개의 양말이 있습니다. 색상 1과 색상 2가 각각 한 켤레 있습니다. 각 색상에 하나씩 3개의 이상한 양말이 남아 있습니다. 쌍의 수는 2입니다.

더미 n에 있는 양말의 수와 각 양말의 색상 배열이 주어지면 몇 켤레가 있습니까?

첫 번째 솔루션:

static int sockMerchant(int n, int[] ar) {
    int pairs = 0;
    HashSet<int> set = new HashSet<int>();
    foreach (int i in ar)
    {
        if (set.Contains(i)) continue;
        int[] matchedItems = Array.FindAll(ar, x => i == x);
        int occurrencies = matchedItems.Length;
        if (occurrencies > 1)
            pairs += ((occurrencies - (occurrencies % 2)) / 2);
        set.Add(i);
    }
    return pairs;
}

두 번째 솔루션:

LINQ를 사용하여 첫 번째 솔루션을 최적화하고 이 또 다른 솔루션을 생각해 낸 at에 첫 번째 솔루션을 표시한 후:

static int sockMerchant(int[] ar)
{
    int pairs = 0;
    int[] colorsCount = ar.GroupBy(color => color).
                Select(color => color.Count()).
                ToArray();
    foreach (int count in colorsCount)
    {
        pairs += ((count - (count % 2)) / 2);
    }
    return pairs;
}

세 번째 솔루션:

보시다시피 두 솔루션 모두 O(N^2)의 복잡성을 가지며 이는 성능에 좋지 않습니다. 그래서 웹에서 조금 더 검색하여 일부 Slack 그룹에 대한 도움을 요청했고 O(N)의 복잡성으로 제안한 다음과 같은 솔루션을 받았습니다.

static int SockMerchant(int[] ar)
{
    var socksPairs = new Dictionary<int, int>();
    int nSocks = 0;
    for (var i = 0; i < ar.Length; i++) {
        var current = ar[i];
        if (socksPairs.ContainsKey(current)) {
            socksPairs[current]++;
            if (socksPairs[current] == 2) {
                nSocks++;
                socksPairs[current] = 0;
            }
        } else {
            socksPairs[current] = 1;
        }
    }
    return nSocks;
}

이 양말 상인 챌린지는 HackerRank의 일부입니다.