👨‍💻 문제

---

✍️ 풀이

🤔 생각

1. 낮은 비용부터 N개 마셔본다. 같은 비용이라면 높은 가치 우선
2. 가치가 부족하다면 다음 낮은 비용을 마신다.
3. N개를 넘었으니 하나를 빼야 한다. -> 가치가 가장 낮은 걸 뺀다. 같은 가치라면 높은 비용 우선

🔀 2개의 우선순위 큐

낮은 비용 순으로 정렬된 맥주들, 입력된 맥주들
낮은 가치 순으로 정렬되는 맥주들, 마실 맥주들

이렇게 2개의 우선순위 큐를 사용한다.

    private static PriorityQueue<Item> items = new PriorityQueue<>((i1, i2) -> {
        if (i1.cost == i2.cost) {
            return - Long.compare(i1.value, i2.value);
        }
        return Long.compare(i1.cost, i2.cost);
    });

    private static PriorityQueue<Item> itemsGotten = new PriorityQueue<>((i1, i2) -> {
        if (i1.value == i2.value) {
            return - Long.compare(i1.cost, i2.cost);
        }
        return Long.compare(i1.value, i2.value);
    });

🍻 맥주 담기

낮은 비용 순으로 정렬되는 우선순위 큐에 입력된 맥주들을
낮은 가치 순으로 정렬되는 우선순위 큐에 맥주들을 다시 담는다.

    private static void getItems() {
        int entireValue = 0;
        while (!items.isEmpty()) {
            // 다음 아이템을 넣는다.
            Item item = items.poll();
            itemsGotten.add(item);
            entireValue += item.value;

            // 수량 초과 시 가장 낮은 가치의 아이템 하나를 버린다.
            if (itemsGotten.size() > itemsCntToGet) {
                entireValue -= itemsGotten.poll().value;
            }

            // 조건을 충족했다면 종료
            if (itemsGotten.size() == itemsCntToGet && entireValue >= requiredValue) {
                return;
            }
        }

        // 조건을 충족하지 못했다면 clear
        itemsGotten.clear();
    }

조건을 충족하지 못했다면 -1을 출력해야 한다.
하지만 이후 조건을 충족하였는지 확인하려면 모든 요소들을 뽑아내어 결과값을 산출해내야 한다.
그러한 과정을 생략하기 위해,

조건을 충족했다면 큐에 요소를 남기고,
충족하지 못했다면 큐를 비워버린다.

---

📄 전체 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class _17503 {

    private static int itemsCntToGet;
    private static int requiredValue;
    private static int itemsCnt;

    private static PriorityQueue<Item> items = new PriorityQueue<>((i1, i2) -> {
        if (i1.cost == i2.cost) {
            return - Long.compare(i1.value, i2.value);
        }
        return Long.compare(i1.cost, i2.cost);
    });

    private static PriorityQueue<Item> itemsGotten = new PriorityQueue<>((i1, i2) -> {
        if (i1.value == i2.value) {
            return - Long.compare(i1.cost, i2.cost);
        }
        return Long.compare(i1.value, i2.value);
    });

    private static class Item {
        long value;
        long cost;

        public Item (long value, long cost) {
            this.value = value;
            this.cost = cost;
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        getItems();
        System.out.println(getResult());
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        itemsCntToGet = Integer.parseInt(st.nextToken());
        requiredValue = Integer.parseInt(st.nextToken());
        itemsCnt = Integer.parseInt(st.nextToken());

        for (int i=0; i<itemsCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int value = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            items.add(new Item(value, cost));
        }
    }

    private static void getItems() {
        int entireValue = 0;
        while (!items.isEmpty()) {
            // 다음 아이템을 넣는다.
            Item item = items.poll();
            itemsGotten.add(item);
            entireValue += item.value;

            // 수량 초과 시 가장 낮은 가치의 아이템 하나를 버린다.
            if (itemsGotten.size() > itemsCntToGet) {
                entireValue -= itemsGotten.poll().value;
            }

            // 조건을 충족했다면 종료
            if (itemsGotten.size() == itemsCntToGet && entireValue >= requiredValue) {
                return;
            }
        }

        // 조건을 충족하지 못했다면 clear
        itemsGotten.clear();
    }

    private static long getResult() {
        if (itemsGotten.isEmpty()) {
            return -1;
        }

        long maxCost = 0;
        while (!itemsGotten.isEmpty()) {
            maxCost = Math.max(itemsGotten.poll().cost, maxCost);
        }
        return maxCost;
    }

}