[프로그래머스] - 과일 장수(C#)

과일 장수

오늘은 "과일 장수" 문제를 풀어보겠습니다. 바로 문제 살펴보겠습니다.

문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과 한 상자의 가격은 다음과 같이 결정됩니다.

한 상자에 사과를 m개씩 담아 포장합니다.
상자에 담긴 사과 중 가장 낮은 점수가 p (1 ≤ p ≤ k)점인 경우, 사과 한 상자의 가격은 p * m 입니다.
과일 장수가 가능한 많은 사과를 팔았을 때, 얻을 수 있는 최대 이익을 계산하고자 합니다.(사과는 상자 단위로만 판매하며, 남는 사과는 버립니다)

예를 들어, k = 3, m = 4, 사과 7개의 점수가 [1, 2, 3, 1, 2, 3, 1]이라면, 다음과 같이 [2, 3, 2, 3]으로 구성된 사과 상자 1개를 만들어 판매하여 최대 이익을 얻을 수 있습니다.

(최저 사과 점수) x (한 상자에 담긴 사과 개수) x (상자의 개수) = 2 x 4 x 1 = 8
사과의 최대 점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻을 수 있는 최대 이익을 return하는 solution 함수를 완성해주세요.

 

제한 사항

• 3 ≤ k ≤ 9
• 3 ≤ m ≤ 10
• 7 ≤ score의 길이 ≤ 1,000,000
• 1 ≤ score[i] ≤ k
• 이익이 발생하지 않는 경우에는 0을 return 해주세요.

 

입출력 예

k	m	score	result
3	4	[1, 2, 3, 1, 2, 3, 1]	8
4	3	[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]	33

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
다음과 같이 사과 상자를 포장하여 모두 팔면 최대 이익을 낼 수 있습니다.

사과상자	가격
[1, 1, 2]	1 x 3 = 3
[2, 2, 2]	2 x 3 = 6
[4, 4, 4]	4 x 3 = 12
[4, 4, 4]	4 x 3 = 12

 

시작 코드

using System;

public class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        return answer;
    }
}

 

나의 풀이

using System;
using System.Linq;

public class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        int index = m - 1;
        Array.Sort(score);
        Array.Reverse(score);
        
        for(int i = 0; i < score.Length / m; i++)
        {
            answer += score[index] * m;
            index += m;
        }
        return answer;
    }
}

 

코드 분석

using 지시문 Linq를 사용하고, int형 정수 k와 m 그리고 배열 score가 주어지며 코드가 시작됩니다.

int형으로 index를 선언하고 m-1을 넣어줍니다. 이어서 score배열을 Array.Sort와 Reverse를 통해 오름차순 정렬하고 뒤집어 줍니다. for문을 i = 0 에서 score의 길이를 m으로 나눈 만큼 돌립니다. 그 안에서 answer에 score[index]에 m을 곱한값을 더해주고, index를 m만큼 증가시켜 줍니다. for문이 끝나면 answer를 리턴하면서 끝이 납니다.

 

풀이 설명

이번 문제도 설명에 비해 비교적 풀이는 간단하게 끝났습니다. 문제에서 원하는 것은 상자에 담긴 (가장 가격이 낮은 과일의 가격) * (상자 속 과일의 개수)로 가격을 책정할 때에, 과일 장수가 얻을 수 있는 최대한의 이익을 구하는 것입니다.

그러므로 최대한 가격이 저렴한 과일끼리 묶어서 상자를 만들어야 합니다. 처음에 설정한 index의 값은 m - 1로, 한 상자 묶음에 마지막 사과가격을 기준으로 움직이는 것을 볼 수 있습니다. 그 작업을 위해 배열을 내림차순으로 만드는 과정이 있습니다. answer에 넣는 값에 m만큼 곱해주고, index에 m을 더해주면서 한 상자에 들어가는 마지막 과일의 가격으로만 계산하는 것을 볼 수 있습니다. 이렇게 계산이 가능한 이유는 내림차순 정렬이 되어있기 때문에 가능한 것입니다.

 

<NEXT>

오늘은 "과일 장수" 문제를 풀어보았습니다. 이제 프로그래머스 레벨 1 문제도 거의 다 풀어갑니다. 레벨1을 마치고 다른 주제를 가지는 새로운 카테고리의 글도 기회가 되면 작성해 볼 생각이 있습니다. 많은 관심 부탁드립니다. 다음에는 완전탐색 카테고리에 속하는 "모의고사" 문제를 다뤄보도록 하겠습니다. 감사합니다.