💡 문제
minimum-number-of-coins-for-fruits (https://leetcode.com/problems/minimum-number-of-coins-for-fruits/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
스택(Stack)과 큐(Queue)는 기본적이면서도 중요한 자료 구조입니다. 이들은 데이터를 저장하고 관리하는 방법을 정의하며, 다양한 알고리즘과 문제 해결에 사용됩니다. 아래에서 스택과 큐의 개념을 설명하겠습니다.
스택
- 재귀적 알고리즘: 함수 호출을 추적하기 위해 스택을 사용합니다.
- 역순 문자열 만들기: 문자열을 역순으로 출력하기 위해 스택을 사용합니다.
- 괄호 검사: 수식의 괄호가 올바르게 닫혔는지 확인하기 위해 스택을 사용합니다.
- 탐색 알고리즘: DFS (깊이 우선 탐색)에 스택을 사용합니다.
큐
- 작업 스케줄링: 작업이 도착한 순서대로 처리해야 할 때 큐를 사용합니다.
- BFS (너비 우선 탐색): 그래프 탐색 알고리즘에서 큐를 사용합니다.
- 프린터 스풀러: 인쇄 작업을 순서대로 처리하기 위해 큐를 사용합니다.
- 캐시 구현: FIFO 캐시를 구현할 때 큐를 사용합니다.
🤓 문제 풀이
🔨 문제 설명
이 문제를 해결하기 위해서는 주어진 과일을 모두 구매하는 데 필요한 최소 코인의 수를 계산해야 합니다. 과일을 구매하면 다음 과일을 무료로 가져갈 수 있다는 규칙이 있으므로, 그리디(탐욕적) 접근법을 사용하는 것이 효과적입니다.
이 접근법은 정렬을 통해 비싼 과일을 먼저 구매하고, 최대한 많은 무료 과일을 가져가는 전략을 사용함으로써 최소한의 코인으로 모든 과일을 구매할 수 있게 합니다.
이 문제는 주어진 가격 배열 prices에서 모든 과일을 얻기 위한 최소 코인의 수를 구하는 문제입니다. 각 과일을 구매하면 다음 과일들 중 하나를 무료로 받을 수 있는 보상을 얻습니다. 따라서 어떤 과일을 구매할지, 어떤 과일을 무료로 받을지를 결정해야 합니다.
🔨 접근 방법
If you purchase the ith fruit at prices[i] coins, you can get any number of the next (i + 1) fruits for free. Note that even if you can take fruit j for free, you can still purchase it for prices[j] coins to receive its reward.
이 문장에서, 특정 과일을 구매하면 그 다음 과일을 무료로 받을 수 있다는 점에 주목했습니다. 그리디 접근법을 통해 비싼 과일을 우선적으로 구매함으로써 최대한 많은 과일을 무료로 가져갈 수 있다는 전략이 유도되었습니다. 이를 통해 비용을 최소화할 수 있습니다.
- 과일 가격 배열을 내림차순으로 정렬 (비싼 과일을 먼저 구매) :
- 비싼 과일을 먼저 구매하면, 그 다음 과일들을 무료로 받을 수 있는 범위가 넓어집니다. 따라서 더 많은 과일을 무료로 받을 수 있습니다.
- 과일 구매 및 무료로 가져가기:
- 정렬된 배열에서 순서대로 과일을 구매하고, 그 다음 과일들을 무료로 가져갑니다. 매 구매마다 해당 과일의 가격을 더하고, 그 다음 과일들을 무료로 가져갑니다.
- 과일을 구매할 때마다 그 다음 과일들을 가능한 최대한 무료로 받음으로써 전체 코인 사용을 최소화할 수 있습니다.
- dp[i] 배열을 사용하여 i 번째 과일까지의 최소 비용을 저장합니다.
- 과일을 구매하고 얻을 수 있는 보상을 고려하여 다음 과일들을 무료로 얻을 수 있는 경우를 체크합니다.
- 각 과일을 구매할 때의 비용과 그로 인해 무료로 얻을 수 있는 과일들을 고려하여 DP 배열을 업데이트합니다.
🔨 문제 풀이 과정
- 가격 배열 내림차순 정렬: 비싼 과일을 먼저 선택하기 위해 prices 배열을 내림차순으로 정렬합니다.
- 구매 과정 시뮬레이션:
- 과일을 구매할 때마다 해당 과일의 가격을 총 코인 수에 더하고, 다음 과일을 무료로 가져갈 수 있는 규칙을 적용합니다.
- 정렬된 배열에서 순차적으로 과일을 구매하고, 구매한 과일의 가격을 총 비용에 더한 후, 그 다음 과일들을 무료로 가져갑니다. 이 과정에서 인덱스를 2씩 증가시켜서 다음 과일을 무료로 가져가는 과정을 구현합니다.
🔨 동적프로그래밍 선택
- 탐욕적 접근법 (Greedy Algorithm): 최적의 솔루션을 찾기 위해 매번 가장 작은 가격의 과일을 구매하는 방식으로 접근할 수 있습니다.
- 다이나믹 프로그래밍 (Dynamic Programming): 각 과일을 구매할 때 얻는 최적의 결과를 저장해나가는 방식으로 접근할 수 있습니다.
여기서는 탐욕적 접근법을 사용하여 문제를 해결합니다. 왜냐하면 과일을 구매할 때마다 이후 과일을 무료로 받을 수 있는 기회를 최대한 활용하는 것이 중요하기 때문입니다.
🔨 구현코드
import java.util.*;
class Solution {
public int minimumCoins(int[] prices) {
int n = prices.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // 시작점
for (int i = 0; i < n; i++) {
// 현재 과일을 구매하는 경우
if (dp[i] != Integer.MAX_VALUE) {
dp[i + 1] = Math.min(dp[i + 1], dp[i] + prices[i]);
// 다음 (i+1)개의 과일을 무료로 얻는 경우
for (int j = i + 1; j <= i + 1 + i && j < n; j++) {
dp[j + 1] = Math.min(dp[j + 1], dp[i] + prices[i]);
}
}
}
return dp[n];
}
}import java.util.*;
class Solution {
public int minimumCoins(int[] prices) {
int n = prices.length;
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0; // 시작점
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// 현재 과일을 구매하는 경우
while (!q.isEmpty() && (q.getFirst() + 1) * 2 < i + 1)
q.removeFirst();
while (!q.isEmpty() && dp[q.getLast()] + prices[q.getLast()] >= dp[i] + prices[i])
q.removeLast();
q.addLast(i);
dp[i + 1] = dp[q.getFirst()] + prices[q.getFirst()];
}
return dp[n];
}
}📚 풀이 보완
코드 설명
- 정렬: Arrays.sort를 사용하여 prices 배열을 내림차순으로 정렬합니다. 이때 Collections.reverseOrder()를 사용하여 큰 값이 앞에 오도록 합니다.
- 구매 시뮬레이션: 정렬된 배열에서 반복문을 통해 과일을 구매합니다. totalCoins에 구매한 과일의 가격을 더하고, 다음 과일은 무료로 가져가기 위해 인덱스를 2씩 증가시킵니다.
- Arrays.sort(prices): 가격 배열을 오름차순으로 정렬합니다. 가장 작은 가격의 과일부터 처리하기 위함입니다.
- int totalCoins = 0: 사용한 총 코인의 수를 저장하는 변수입니다.
- int i = 0: 현재 과일의 인덱스를 저장하는 변수입니다.
- while (i < prices.length): 배열의 끝까지 순회합니다.
- totalCoins += prices[i]: 현재 과일의 가격을 총 코인 수에 더합니다.
- i += 2: 현재 과일을 구매한 후, 다음 과일(최대 i+1 과일까지)을 무료로 받습니다. 따라서 다음 구매할 과일의 인덱스는 i+2가 됩니다.
동적 프로그래밍 코드 설명
코드 설명
- dp 배열은 각 인덱스마다 그 과일까지 구매하는 데 필요한 최소 코인의 수를 저장합니다.
- dp[0]은 첫 번째 과일을 구매하는 비용으로 초기화합니다.
- dp[i]를 계산할 때, 이전 과일까지의 최소 비용과 현재 과일을 구매하는 비용을 더합니다.
- 다음 과일들을 무료로 받을 수 있는 경우를 고려하여 dp[i + j]를 업데이트합니다.
- 마지막으로 dp[n - 1]에 저장된 값이 모든 과일을 구매하는 데 필요한 최소 코인의 수입니다.
📍 Plus+
시간 복잡도
- 외부 루프: for (int i = 0; i < n; i++)
- 이 루프는 n번 반복됩니다.
- 내부 루프: for (int j = i + 1; j <= i + 1 + i && j < n; j++)
- 내부 루프는 i가 증가함에 따라 반복 횟수가 다릅니다. 최악의 경우에서 내부 루프는 약 i번 반복될 수 있습니다.
내부 루프의 합을 계산하면, 첫 번째 반복에서 1번, 두 번째 반복에서 2번, ..., n번째 반복에서 n번 수행됩니다. 이는 등차수열의 합으로, O(n^2)입니다.
공간 복잡도
- DP 배열: int[] dp = new int[n + 1];
- dp 배열은 크기가 n + 1입니다.
이외에 추가적인 큰 공간을 사용하지 않으므로, 공간 복잡도는 다음과 같습니다:
요약
- 시간 복잡도: O(n^2)
- 공간 복잡도: O(n)