목표
문제를 보면서 어떻게 해결해야할지 스스로 고민해보는것같다. 조금더 고민해서 코드를 작성할 수 있도록 노력중이다.
문제
내가 생각했을때 문제에서 원하는부분
과일 장수가 사과 상자를 포장하고 있다. 사과는 상태에 따라 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 함수 완성내가 이 문제를 보고 생각해본 부분
주어진 score 배열을 정렬하는 것이 가장 기본적이다. 내림차순 정렬을 하면 큰 점수 순서대로 접근할 수 있다.
정렬된 배열의 특성을 이용하면, 뒤에서부터 m개씩 거꾸로 접근하면 현재 위치에서 m만큼 떨어진 곳(index에서 -m한 곳)이 가장 낮은 점수가 된다.
즉 그 값(score[i - m])이 현재 상자의 최소 점수가 되며, 이에 m을 곱하면 해당 상자의 가격을 구할 수 있다.
이를 전체 배열에 대해 반복하며 모든 가격을 더하면, 사용 가능한 최대 사과로 구성된 상자들의 조합 중 최대값을 구할 수 있다.
별도의 minScore 변수 없이 한 줄로 해결할 수 있다는 점에서 매우 간결하다.코드로 구현
import java.util.*;
class Solution {
public int solution(int k, int m, int[] score) {
Arrays.sort(score);
int answer = 0;
for(int i = score.length; i >= m; i -= m){
answer += score[i - m] * m;
}
return answer;
}
}정렬된 배열의 성질을 이용
뒤에서부터 m개씩 접근하며 가장 낮은 값 찾기
가격 계산 및 누적
한 줄로 간결하게 표현시간복잡도 O(NlogN)이다.
장점
정렬된 배열의 성질을 잘 이용해서 간결하고 이해하기 쉬운 코드이다.
한 줄의 코드로 핵심 로직을 구현할 수 있다.
추가 메모리를 전혀 사용하지 않아 메모리 효율이 좋다.
단점
입력 배열을 정렬해야 하므로 제자리 정렬이 아닌 경우 O(NlogN)의 추가 시간 복잡도가 발생할 수 있다.
코드가 너무 간결해서 이해하기 어려울 수 있다.
문제 조건이나 엣지 케이스를 고려하지 못할 수 있다.
마무리
주말에도 문제를 해결하고 나니깐 조금 어렵게 느껴졌던 문제가 차근차근 해결하니깐 조금씩 자신감이 생기는것같다.
Junior backend developer