[프로그래머스 | C#] 과일 장수 Sort

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

프로그래머스

문제

이번 문제는 프로그래머스에서 보는 게 좋다.

그러니 바로 코드로 들어간다.

코드

using System;

namespace ConsoleApplication1
{
    public class 과일_장수
    {
        // static void Main()
        // {
        //     Console.WriteLine(solution(3, 4, new int[] {1, 2, 3, 1, 2, 3, 1}));
        // }
        
        public static int solution(int k, int m, int[] score) {
            int maxValue = 0;
            int index = score.Length - 1;
            Array.Sort(score);
            while (index - m + 1 >= 0)
            {
                maxValue += m * score[index - m + 1];
                index -= m;
            }
            return maxValue;
        }
    }
}

m개의 과일이 들어가는 과일 상자를 채우는데, 과일 상자를 채워서 최대의 이익을 내려면 과일이 든 배열을 정렬해서 큰건 큰 것끼리, 작은 건 작은 것끼리 둬야 큰 수가 작은 수에 의해 가려지는 불상사가 일어나지 않는다.

 

1. 따라서 Array.Sort로 과일 배열 score를 오름차순 정렬한다.

오름차순 정렬했으니 예시 배열인 [1, 2, 3, 1, 2, 3, 1]는 [1, 1, 1, 2, 2, 3, 3]이 된다.

그럼 가장 최대의 이익을 내는 상자의 경우는 [1, 1, 1] [2, 2, 3, 3] 이다.

이때 상자를 가득 채워야 내다 팔 수 있다. [1, 1, 1]은 상자를 다 채우지 못했으므로 이익에 들어가지 못한다.

 

2. 상자를 채우지 못하는 경우([1, 1, 1])를 유의하며 while 문으로 각 상자의 이익을 계산한다.

나는 배열의 마지막부터 첫번째까지 while로 일정 구간씩(상자에 들어가는 과일 수 만큼) 점프하며 이익을 계산하려고 한다.

이때 index - m + 1은 현재 내가 확인하고 있는 인덱스이다. 이 인덱스는 현재 상자에서 가장 작은 값을 가지고 있다.

[1, 1, 1, 2, 2, 3, 3]에서 첫번째 2를 가리킨다는 의미이다. (오름차순 정렬된 배열의 뒤에서부터 보므로 2, 2, 3, 3이 상자에 들어감)

가장 작은 수인 2와 상자 안 과일 수 4를 곱하면 8이다.

 

3. 상자를 다 채우지 못하면 이익에서 제외한다.

while문을 탈출한다는 소리이다. 남은 과일은 그냥 무시하고, maxValue(최대 이익)를 반환한다. 

 

Sort

보통 List.Sort<T>를 많이 쓰는 것으로 알고 있는데, 배열에서 Sort를 쓰는 방법이 있나해서 알아보았다.

https://learn.microsoft.com/ko-kr/dotnet/api/system.array.sort?view=net-7.0 

Array.Sort 메서드 (System)

 

아래는 List.Sort<T> 문서

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=net-7.0 

List<T>.Sort Method (System.Collections.Generic)