[BOJ] 백준 3691 : 컴퓨터 조립 (java)

🧪 3691 컴퓨터 조립

---

난이도 : 🌟 골드 3
유형 : 구현 | 자료구조

https://www.acmicpc.net/problem/3691

 

📝 문제

---

상근이는 술을 먹던 도중 프로그래밍을 못하는 이유를 갑자기 깨달았다. 그 이유는 바로 상근이의 컴퓨터 성능이 좋지 않았기 때문이다. 상근이는 컴퓨터를 사기로 결심했다.

상근이는 컴퓨터를 조립해서 만들 것이다. 따라서, 각 부품을 모두 따로 구매해서 직접 조립해야 한다. 각각의 부품은 하나씩 구매하면 된다.

컴퓨터의 성능은 가장 안 좋은 부품의 성능과 같다. 따라서, 상근이는 예산을 초과하지 않으면서 가장 안 좋은 부품의 성능을 최대로 하려고 한다.

각 부품의 이름과 종류, 성능이 주어진다. 이때, 상근이의 예산으로 구매할 수 있는 가장 성능이 좋은 컴퓨터를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 부품의 개수 n과 상근이의 예산 b가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ b ≤ 1,000,000,000)

다음 n개 줄에는 부품의 정보가 "type name price quality"와 같은 형식으로 주어진다. type은 부품의 종류, name은 그 부품의 이름, price는 가격 (0 ≤ price ≤ 1,000,000), quality는 성능 (0 ≤ quality ≤ 1,000,000,000)이다.

부품의 이름은 겹치지 않고, 성능은 숫자가 높을수록 좋은 것이다. 문자열에는 글자와 숫자, 그리고 밑 줄만을 포함하며, 최대 길이는 20글자이다.

항상 주어진 예산으로 컴퓨터를 조립할 수 있는 경우만 입력으로 주어진다.

 

출력

 

 

각 테스트 케이스에 대해서, 상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터의 성능을 출력한다.

 

🚧  주의할 점

---

1) 가장 낮은 성능을 올려주는 것이 최우선이기 때문에 결과값을 담는 큐는 성능 기준 오름차순으로 정렬한다.

 

🧐 핵심 로직 

---

1. 각 부품을 hashmap에 제품의 이름을 key로 arraylist에 저장할 위치번호를 value로 저장한다.

 

2. arraylist의 속성을 우선순위 큐로 해서 각각의 부품을 가격순으로 정렬한다.

 

3. 모든 부품을 선택하기 위해 각각의 arraylist에 꺼내어 새로운 우선순위 큐에 저장한다.

    3 - 1) 이때는 성능이 낮은 부품을 꺼내야 하기 때문에 성능 순으로 정렬되게 한다.

 

4. 성능이 낮은 부품을 꺼내 해당 부품에서 가격이 낮고 자신보다 성능이 높은 것이 나올 때까지 진행한다.

 

5. 성능이 높은 것이 존재하지 않으면 현재 낮은 것을 결과로 저장한다.

 

💻 최종 코드 (480 ms)

---

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

public class Main {

    static class Product implements Comparable<Product> {

        int num, price, value;

        Product (int num, int price, int value) {
            this.num = num;
            this.price = price;
            this.value = value;
        }

        @Override
        public int compareTo(Product o) {

            int cmp = Integer.compare(this.price, o.price);
            if (cmp == 0) {
                return Integer.compare(o.value, this.value);
            }

            return cmp;
        }
    }

    static class SelectProduct implements Comparable<SelectProduct> {

        int num, price, value;

        SelectProduct (int num, int price, int value) {
            this.num = num;
            this.price = price;
            this.value = value;
        }

        @Override
        public int compareTo(SelectProduct o) {

            int cmp = Integer.compare(this.value, o.value);

            return cmp;
        }
    }

    static BufferedReader br;
    static int n, b, sum, ans;
    static HashMap<String, Integer> types;
    static List<PriorityQueue<Product>> products;
    static PriorityQueue<SelectProduct> results;
    public static void main(String[] args) throws Exception {

//      br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new FileReader("input.txt"));

        int t = Integer.parseInt(br.readLine());
        for (int testCase = 1; testCase <= t; testCase++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st1.nextToken());
            b = Integer.parseInt(st1.nextToken());

            sum = 0;
            types = new HashMap<>();
            products = new ArrayList<>();
            results = new PriorityQueue<>();

            for (int i = 0; i < n; i++) {
                insertData();
            }

            init();
            calculate();
            System.out.println(ans);
        }

        br.close();
    }

    private static void insertData() throws Exception {

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        String pc = st2.nextToken();
        st2.nextToken();
        int price = Integer.parseInt(st2.nextToken());
        int value = Integer.parseInt(st2.nextToken());

        if (types.get(pc) != null) {
            int num = types.get(pc);
            products.get(num).add(new Product(num, price, value));
        } else {
            int num = types.size();
            types.put(pc, num);
            products.add(new PriorityQueue<>());
            products.get(num).add(new Product(num, price, value));
        }
    }

    private static void init() {

        for (PriorityQueue<Product> product : products) {
            Product next = product.remove();
            results.add(new SelectProduct(next.num, next.price, next.value));
            sum += next.price;
        }
    }

    private static void calculate() {

        while (true) {
            SelectProduct selectProduct = results.remove();
            sum -= selectProduct.price;
            boolean flag = false;

            while (!products.get(selectProduct.num).isEmpty()) {
                Product next = products.get(selectProduct.num).remove();
                if (sum + next.price <= b && next.value > selectProduct.value) {
                    sum += next.price;
                    results.add(new SelectProduct(next.num, next.price, next.value));
                    flag = true;
                    break;
                }
            }

            if (!flag) {
                ans = selectProduct.value;
                return;
            }
        }
    }
}