[99클럽 코테 스터디 26일차 TIL] 큐

📖 오늘의 학습 키워드
큐

오늘의 회고

문제

[Minimum Number of Coins for Fruits]
https://leetcode.com/problems/minimum-number-of-coins-for-fruits/description/

나의 해결

class Solution {
    public int minimumCoins(int[] prices) {
        int len = prices.length;
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = len; i > 0; i--) {
            while(!q.isEmpty() && q.peek() > i * 2 + 1) {
                q.poll();
            }
            if(i <= (len - 1) / 2) {
                prices[i - 1] += prices[q.peek() - 1];
            }
            while(!q.isEmpty() && prices[q.peekLast() - 1] >= prices[i - 1]) {
                q.pollLast();
            }
            q.offer(i);
        }
        return prices[0];
    }
}

1. prices 배열 내 원소의 순서를 저장할 Deque q를 선언한다. 삭제를 양쪽으로 수행하기 위해 Deque을 사용한다.
2. i가 len(배열의 길이)부터 1까지 for 문을 돌며 i번째부터 끝까지 모든 과일을 샀을 때 필요한 최소 동전의 수를 계산한다.
3. q가 비어있지 않고, 맨 앞의 값이 i * 2 + 1보다 크다면 해당 값을 사용할 수 없으므로 그런 값이 없을 때까지 q에서 제거한다.
4. i가 (len - 1) / 2보다 크지 않다면 prices[i - 1]에 prices[q.peek() - 1] 값을 더한다.
5. q가 비어있지 않고, 맨 뒤의 요소에 해당하는 과일의 가격이 i번째 과일의 가격보다 크다면 마지막 요소를 q에서 제거한다.
6. q에 i를 추가한다.
7. 모든 과일을 살 때 필요한 최소 동전의 개수이므로 prices[0]를 마지막에 정답으로 반환한다.