-
[프로그래머스, Lv1] 과일장수알고리즘 문제/Java 2024. 7. 30. 22:51
코딩테스트 연습 - 과일 장수 | 프로그래머스 스쿨 (programmers.co.kr)
문제설명
과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 해주세요
접근 방법
해당 문제를 처음 접했을 때에는 해당 문제가 조합 문제인가 헷갈렷었다.
하지만, 고민을 해보니 높은 등급의 과일만 모아 놓는 것이 제일 효율적이라는 생각이 들었다.
예를들어 [ 7, 6, 5, 4, 3, 2 ] 이라는 과일들을 3개의 상자로 나눠 담을 경우
[ 7 6, 5 4, 3 2 ] = 24원
[ 7 5, 6 4, 3 2 ] = 22원과 같이
제일 높은 등급 순서대로 넣은 것이 제일 비쌌다.
해당 내용을 기억한채 구현은 이러했다.
- 배열을 정렬한다.
- 배열의 마지막위치 - [ 상자내 사과 개수( m ) ] 위치부터 거꾸로 올라가며, 사과 가격 * m을 해준다.
- 해당 값을 모두 더한다
최종 코드
더보기import java.util.*; class Solution { public int solution(int k, int m, int[] score) { int answer = 0; Arrays.sort(score); for(int i = score.length - m; i >= 0; i -= m) { answer += score[i] * m; } return answer; } }
'알고리즘 문제 > Java' 카테고리의 다른 글
[프로그래머스, Lv1] 소수 만들기 (0) 2024.08.01 [프로그래머스, Lv1] 모의고사 (0) 2024.07.31 [프로그래머스, Lv1] 카드뭉치 (0) 2024.07.29 [프로그래머스, Lv1] 명예의 전당(1) (1) 2024.07.24 [프로그래머스, Lv1] K번째 수 (0) 2024.07.23