AOJ - 97 딸기모찌 [java] - Dequeue

핵심 아이디어

먼저 산 것부터 먹는다 = Queue (FIFO)

단, 같은 종류를 여러 개 살 때 하나씩 넣으면 V가 2억이라 메모리 초과 → {종류, 개수} 묶음으로 저장.

---

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int Q = Integer.parseInt(st.nextToken());
        long V = Long.parseLong(st.nextToken()); // 냉장고 최대 용량

        // {종류, 개수} 묶음으로 저장하는 큐
        Deque<long[]> fridge = new ArrayDeque<>(); // [종류, 개수]
        long current = 0; // 현재 냉장고에 있는 총 개수

        StringBuilder sb = new StringBuilder();

        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());

            if (op == 1) {
                // 1 x y: x종류 y개 구입
                int x = Integer.parseInt(st.nextToken());
                long y = Long.parseLong(st.nextToken());

                // 냉장고에 넣을 수 있는 개수 계산
                long canStore = Math.min(y, V - current);

                if (canStore > 0) {
                    fridge.addLast(new long[]{x, canStore});
                    current += canStore;
                }

            } else if (op == 2) {
                // 2 y: 오래된 것부터 y개 먹기
                long y = Long.parseLong(st.nextToken());
                long toEat = Math.min(y, current); // 실제 먹을 수 있는 개수
                current -= toEat;

                while (toEat > 0 && !fridge.isEmpty()) {
                    long[] front = fridge.peekFirst();

                    if (front[1] <= toEat) {
                        // 앞 묶음 전부 먹기
                        toEat -= front[1];
                        fridge.pollFirst();
                    } else {
                        // 앞 묶음 일부만 먹기
                        front[1] -= toEat;
                        toEat = 0;
                    }
                }

            } else {
                // 3: 가장 먼저 산 종류 출력
                if (fridge.isEmpty()) {
                    sb.append(-1).append('\n');
                } else {
                    sb.append(fridge.peekFirst()[0]).append('\n');
                }
            }
        }

        System.out.print(sb);
    }
}

---

흐름 요약

큐에 [종류, 개수] 묶음으로 저장

1번: 넣을 수 있는 만큼만 계산 → addLast()
2번: 앞에서부터 y개 제거
      └─ 묶음 개수 <= y → 묶음 통째로 제거
      └─ 묶음 개수 > y  → 묶음 개수만 줄이기
3번: peekFirst()[0] 출력

왜 ArrayDeque? V가 최대 2억이라 딸기모찌를 하나씩 넣으면 메모리 초과. 같은 종류는 [종류, 개수] 묶음으로 저장해서 해결. ArrayDeque가 LinkedList보다 빠르고 메모리도 적게 씁니다.

 

 

묶음 설명

예제로 보면:

1 1 5  → 1번 종류 5개 구입

하나씩 넣으면:

fridge = [1, 1, 1, 1, 1]  ← 1이 5개

묶음으로 넣으면:

fridge = [[1, 5]]  ← "1번 종류가 5개" 를 하나로 묶음

1 2 5  → 2번 종류 5개 구입 (근데 공간 3개만 남음)

묶음으로 넣으면:

fridge = [[1, 5], [2, 3]]  ← "2번 종류가 3개"

---

왜 묶음으로 넣냐면

V가 최대 2억입니다.

1 1 200000000  → 1번 종류 2억개 구입

하나씩 넣으면 배열에 2억 개 원소 → 메모리 초과

묶음으로 넣으면 [[1, 200000000]] → 원소 1개

---

코드에서 보면

// [종류, 개수] 배열 하나가 묶음 하나
fridge.addLast(new long[]{x, canStore});
//                         종류  개수

fridge = [
    [1, 5],   ← 1번 종류 5개
    [2, 3]    ← 2번 종류 3개
]

먹을 때는 앞 묶음의 개수를 줄이다가 0이 되면 그 묶음을 제거하는 방식입니다.