프로그래밍 일기 — 과일 장수 수수께끼
알고리즘 문제가 갈수록 어려워진다…
알고리즘 문제를 푸는 습관을 들이기 위해 매일 같이 노력하고 있다. 하지만, 이제 Level 2문제를 마주하면서 점점 더 어려워짐을 느낀다. 오늘 도전한 문제는 사실 지난 3일간 노력해 본 것인데 도저히 풀리지 않아 다른 사람의 답변을 참고했다.
이럴 때마다 큰 아쉬움을 느낀다. 내가 아직 이 정도 수준의 문제를 풀기 힘들 정도로 똑똑하지 못한가하는 자책감도 든다. 하지만 어쩌겠는가? 넘어저도 결승점을 향해 계속 달리는 수밖에 없다. 다행히도 삶은 나중에 들어오더라도 완주한 사람도 승자로 취급해준다. 그러니 그것에 감사하며 오늘도 한발 더 나아가기 위해 노력한다.
지난 3일 동안 나를 괴롭혔던 과일 장수 문제(2)를 다른 사람의 블로그를 참고(거의 배껴서) 해결했다. 하지만 그 원리가 무엇이었는지를 이해하기 위해 어떤식으로 문제에 접근했는지를 설명한다.
문제 설명
과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 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 해주세요.
입출력 예제
- 예제 1:
k= 3,m= 4,score= [1, 2, 3, 1, 2, 3, 1] → 2 x 4 x 1 = 8 - 예제 2:
k= 4,m= 3,score=
[4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2] → (1 x 3 x 1) + (2 x 3 x 1) + (4 x 3 x 2) = 33
문제 해설
이 문제는 주어진 score 배열 내에서 최소값으로 m 개 만큼의 배열을 생성하여 각 배열 내에서 최소 값과 그 배열의 요소의 수 m 값 그리고 만들어진 배열을 곱해 그 결과를 반환해야하는 문제다. 그렇다면 아래와 같은 접근을 해 볼 수 있다.
- 배열을 먼저 작은 값에서 큰 값으로 정렬한다
일단 배열을 정렬해본다. 첫 번째 예제는 [1, 1, 1, 2, 2, 3, 3]으로 정렬 될 것이다. 그렇게되면 가장 큰 값이 맨 뒤로간다.
2. 맨 끝의 배열 위치에서 내림차순으로 m 의 인덱스에 닿을 때까지 역방향 순회한다.
가장 끝 위치 index = 7일 것이다. 여기서 m의 인덱스 위치까지면 m = 4까지간다.
3. 각 위치를 순회하면서 각 위치에 해당하는 인덱스에 m의 값을 빼준 값을 곱하고(m * score[i -m] ), 그 값을 더한다( sum += m * score[i — m] ).
k = 4, m = 3, score = [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]이 주어졌다고 했을 때, 배열은 [1,1,2,2,2,2,4,4,4,4,4,4]
- 3 * score[12–3 = 9] = 3 * 4 = 12
- 3 * score[9–3 = 6] = 3 * 4 = 12
- 3 * score[6–3 = 3] = 3 * 2 = 6
- 3 * score[3–3 = 0] = 3 * 1= 3
결과값 : 12 + 12 + 6 + 3 = 33
즉, 각 위치를 순회할 때마다 현재 위치에서 m만큼 왼쪽으로 위동하고, 해당 위치의 값을 m 과 곱해 결과 값을 합산하는 것이다. 이런식으로 가면 위 문제에서 설명한 것과 같은 답을 마지막에 얻을 수 있다. 코드를 보면 아래와 같다.
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public int solution(int k, int m, int[] score) {
// 1. 배열을 작은 값에서 큰 값으로 정렬
Arrays.sort(score);
int answer = 0;
// 2. 배열의 끝에서 m까지 순회
for(int i = score.length; i >= m; i -= m){
// 3. 사실상 배열의 현재 위치에서 m 만큼 왼쪽으로 이동하면서 그 위치의 값을 m과 곱해 합산한다.
answer += m * score[i - m];
}
return answer;
}
}참조:
(1) https://pixabay.com/illustrations/stone-push-overcoming-obstacle-2127669/
(2) https://school.programmers.co.kr/learn/courses/30/lessons/135808
