[백준]#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
18 800
processor 3500_MHz 66 5
processor 4200_MHz 103 7
processor 5000_MHz 156 9
processor 6000_MHz 219 12
memory 1_GB 35 3
memory 2_GB 88 6
memory 4_GB 170 12
mainbord all_onboard 52 10
harddisk 250_GB 54 10
harddisk 500_FB 99 12
casing midi 36 10
monitor 17_inch 157 5
monitor 19_inch 175 7
monitor 20_inch 210 9
monitor 22_inch 293 12
mouse cordless_optical 18 12
mouse microsoft 30 9
keyboard office 4 10

예제 출력 1

9

풀이

이 문제는 우선순위 큐와 해쉬맵을 이용해서 풀 수 있었다. 항상 주어진 예산으로 컴퓨터를 조립할 수 있다고 조건이 있기 때문에 각 부품 중 가격이 가장 작은 것들을 이용해서 컴퓨터 조립 후, 조립된 컴퓨터의 부품 중 성능이 가장 낮은 부품을 예산 내에서 교체한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int test_case=0; test_case<T; test_case++) {
            HashMap<String, PriorityQueue<Product>> map = new HashMap<>();
            String[] input = br.readLine().split(" ");
            int n = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);

            for(int i=0; i<n; i++) {      //부품을 카테고리 별로 정리
                input = br.readLine().split(" ");
                String label = input[0];

                if(map.containsKey(label)) {
                    map.get(label).add(new Product(Integer.parseInt(input[2]), Integer.parseInt(input[3])));    
                }

                else {
                    map.put(label, new PriorityQueue<>());
                    map.get(label).add(new Product(Integer.parseInt(input[2]), Integer.parseInt(input[3])));
                }
            }

            sol(map, b);
        }
    }

    public static void sol(HashMap<String, PriorityQueue<Product>> map, int budget) {
        PriorityQueue<Product2> pq2 = new PriorityQueue<>();

        for(String name : map.keySet()) {     //가장 적은 예산으로 가능한 컴퓨터 조립
            Product p = map.get(name).poll();

            budget -= p.price;
            pq2.add(new Product2(name, p.price, p.quality));
        }

        while(true) {           //성능이 좋은 부품으로 교체
            String label = pq2.peek().name;

            while(!map.get(label).isEmpty() && map.get(label).peek().quality<=pq2.peek().quality) {     //성능이 더 좋은 부품 찾기
                map.get(label).poll();
            }

            if(map.get(label).isEmpty()) break;   //교체할 부품 없으면 끝냄

            int price1 = pq2.peek().price;
            int price2 = map.get(label).peek().price;

            if(budget+price1-price2>=0) {       //예산 내에 교체 가능하면 
                pq2.poll();
                Product p = map.get(label).poll();
                pq2.add(new Product2(label, p.price, p.quality));
                budget += price1-price2;
            }

            else break;     //교체할 부품 없으면 끝냄
        }

        System.out.println(pq2.peek().quality);
    }

    public static class Product implements Comparable<Product>{     //가격순으로 정렬하는 클래스
        int price;
        int quality;

        public Product(int price, int quality) {
            this.price = price;
            this.quality = quality;
        }

        public int compareTo(Product p) {
            return this.price > p.price ? 1 : -1;
        }
    }

    public static class Product2 implements Comparable<Product2>{     //성능순으로 정렬하는 
        String name;
        int price;
        int quality;

        public Product2(String name, int price, int quality) {
            this.name = name;
            this.price = price;
            this.quality = quality;
        }

        public int compareTo(Product2 p) {
            return this.quality > p.quality ? 1 : -1;
        }
    }
}