[Lv.1] 과일 장수 [프로그래머스_코딩테스트]

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

프로그래머스

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// 과일 장수
    /// https://school.programmers.co.kr/learn/courses/30/lessons/135808
    /// </summary>
    public int solution(int k, int m, int[] score)
    {
        var scoreList = new List<int>(score);
        
        int answer = 0;
        
        // 가장 큰 것들부터 우선순위 정렬
        scoreList.Sort((a, b) => b.CompareTo(a));

        int count = 0;
        
        foreach (var target in scoreList)
        {
            count++;

            if (count >= m)
            {
                answer += (m * target);
                count = 0;
            }
        }
        
        return answer;
    }
}

/// <summary>
/// C# 7.3
/// </summary>
internal class Program
{
    public static void Main(string[] args)
    {
        var sl = new Solution();
        int k = 4;
        int m = 3;
        var score = new [] { 4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2 };
        Console.WriteLine(sl.solution(k, m, score));
    }
}

 

Greedy 를 적용해서 가장 큰 Score들부터 내림차순 정렬 후 고정된 개수끼리 박스에 묶고 최종 점수를 알아내는 방법.

단순하게 생각했던 부분이긴 해서 좀 더 다듬을 방법을 ChatGpt에게 물어보았고 나온 방향

 

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public int solution(int k, int m, int[] score)
    {
        // 1. 점수 내림차순 정렬
        Array.Sort(score, (a, b) => b.CompareTo(a));

        int totalProfit = 0;
        int boxCount = score.Length / m;

        for (int i = 0; i < boxCount; i++)
        {
            // 2. score 배열 중에서 m개씩 슬라이싱 (복사 없이)
            var segment = new ArraySegment<int>(score, i * m, m);

            // 3. 해당 상자의 최소 점수를 구하고, 이익 계산
            int minScore = segment.Min(); // LINQ 사용 가능
            totalProfit += minScore * m;
        }

        return totalProfit;
    }
}

 

일단 모든 스코어를 다 도는 방향에서 박스의 개수만큼 for를 돌리고 ArraySegment를 활용 후 최소 값을 계산해서 최대 이익을 더하는 것으로 보인다.

 

다만 이러한 방향은 여전히 GC를 발생할 수 있는 것이라 보여서 한 번 더 정리

 

public class Solution
{
    public int solution(int k, int m, int[] score)
    {
        // 오름차순 정렬 후 뒤집기 → GC-free
        Array.Sort(score);
        Array.Reverse(score);

        int totalProfit = 0;
        int boxCount = score.Length / m;

        for (int i = 0; i < boxCount; i++)
        {
            int min = int.MaxValue;
            for (int j = 0; j < m; j++)
            {
                int val = score[i * m + j];
                if (val < min) min = val;
            }

            totalProfit += min * m;
        }

        return totalProfit;
    }
}

 

Array.Sort 자체에서 GC가 발생하진 않지만 안에 정렬 람다식이 들어가면서 delegate 전달이 되면서 gc가 발생한다고 한다. 그래서 Sort 후 Reverse를 하는 형태로 내림차순을 한다고 하고. Linq는 대표적이게 GC 유발을 하는 것이기에 최소값도 직접 구한 것으로 보임.

 

그리고 위에서 최소값을 반복을 또 돌리고 있지만 이건 무의미한 게 박스의 마지막 항목이 내림차순되어 있어서 늘 최소값이기에 그걸로 하면 반복을 1번으로 돌릴 수 있다.

 

public class Solution
{
    public int solution(int k, int m, int[] score)
    {
        // 오름차순 정렬 후 뒤집기 (내림차순)
        Array.Sort(score);
        Array.Reverse(score);

        int totalProfit = 0;
        int boxCount = score.Length / m;

        for (int i = 0; i < boxCount; i++)
        {
            // 각 상자의 최소값은 항상 m번째 사과
            int min = score[i * m + (m - 1)];
            totalProfit += min * m;
        }

        return totalProfit;
    }
}

 

그렇게 나온 최적의 결과물은 요렇게 된다.

 

추가로 Array.Sort((a, b) => b.CompareTo(a))를 해서 내림차순 한거 보다 Array.Sort() 후 Array.Reverse()를 하는 게 GC도 없고 속도도 더 빠르다고 한다. (대량의 요소들을 정렬할 때에는 좀 더 염두에 두고 하는 것이 나을 듯 하다)