[프로그래머스] 코딩테스트 연습 - 과일장수 (Java, C)

-링크

https://school.programmers.co.kr/learn/courses/30/lessons/135808?language=java 

프로그래머스

 

 

-문제 설명

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 해주세요.

 

-입출력 예

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

 

 

 

 

-해설(Java)

이 문제는 K의 존재에 대해 고민이 많았다. 파라미터로 K를 주어줬지만 필요성에 대해 여러번 생각 해 보았지만 문제를 풀어 답을 도출 해 낼 때 까지도 K의 존재를 이해하지 못했기 때문이다..

우선 문제의 설명에서는 K를 가지고 설명을 하기 때문에 이해하기 어려웠지만, 다시 설명 해 보자면 주어진 score를 정렬하여 한 박스에 담아야 하는 과일의 개수(m)로 나누고, 판매할 수 있는 박스의 수와 최저 score와 과일의 개수(m)을 곱하여 나온 값을 모두 더하여 return하면 되는 것이다.

아래 풀이에서는 Arrays.sort를 통해 int배열을 내림차순으로 정렬하였다.

내림차순으로 정렬했기 때문에 배열의 맨 끝자리 부터 접근하였고, for문의 조건으로는 정렬한 과일을 큰 순서로 담았을 경우 박스 안의 최소 점수의 인덱스에 접근하기 위해 과일의 개수(score의 길이)-과일의 개수(m)으로 시작하여 과일의 개수(m)씩 차감하도록 작성하였다. for문이 도는 limit으로는 score의 길이를 과일의 개수로 나눈 나머지 -1로 주었다.(총 과일의 개수를 한 박스에 들어가야 하는 과일의 개수로 나눴을 때의 나머지의 바로 윗 인덱스 까지 접근)

복잡한 코드 작성없이 풀이를 완료하였다.

 

 

-Java 풀이

import java.util.Arrays;

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

        Arrays.sort(score);
        for(int i=score.length-m; i > score.length%m-1; i-=m)
            answer+=score[i]*m;
        
        return answer;
    }
}

 

 

 

-해설(C)

세부적인 코드의 구성은 위에서 설명한 Java해설과 동일합니다.

다만 C코드로 작성할 때에는 qsort를 사용하여 정렬하였으며, 내림차순이 아닌 오름차순으로 정리하여 첫 인덱스부터 접근하였고 오름차순에 따른 마지막 검사 인덱스와 i의 인덱스 변화를 과일의 개수(m)만큼 더하여 접근하도록 하여 한 박스의 최소 점수를 구한 후 답을 도출하였다.

 

 

-C풀이

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int static sort(const void *a, const void *b){
    return *(int *)b - *(int *)a;
}

// score_len은 배열 score의 길이입니다.
int solution(int k, int m, int score[], size_t score_len) {
    int answer = 0;
    
    qsort(score, score_len, sizeof(int), sort);
    
    for(int i = m-1; i < score_len - (score_len%m); i+=m)
        answer += score[i]*m;
    
    return answer;
}