3691 컴퓨터조립 - 백준

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

3691번: 컴퓨터 조립

풀이

첫째 줄 테스트 케이스: 100개를 넘지 않음

첫째 줄

부품의 갯수: n  예산 b

n개의 줄

부품의 정보

type: 부품의 종류, name: 부품의 이름, price: 가격, quality: 성능

 

상근이의 예산으로 구매할 수 있는 가장 좋은 컴퓨터 성능

 

hashmap에 저장

<제품 이름: list 번호>

list 구성

순서대로 가격과 성능을 정렬한 순서대로 정렬

각각의 가격 성능 list를 가격이 낮은 순으로 오름차순 정렬

일단 전부 가장 낮은걸로 부품들을 넣는다.

이후 성능 낮은 부품을 꺼내서 해당 부품에서 가격이 낮고 자기보다 성능 높은 것이 나올때까지 반복한다.

성능 높은 게 존재하지 않으면 현재 상황에서 값을 결과로 저장한다.

코드

package test3691;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.StringTokenizer;

public class Main {

	static Map<String, Integer> computer; // 컴퓨터 정보 저장

	static ArrayList<PriorityQueue<minHeap>> pcList;// 순서대로 담을 거
	static PriorityQueue<minHeap2> result; // 가치가 작은걸 뺄거다.
	static int TC;
	static int n; // 부품
	static int b; // 예산
	static int sum;
	static int resultvalue;

	public static class minHeap implements Comparable<minHeap> { // 가격순 정렬
		int num;
		int money;
		int value;

		public minHeap(int num, int money, int value) {
			this.num = num;
			this.money = money;
			this.value = value;
		}

		@Override
		public int compareTo(minHeap o) {
			// TODO Auto-generated method stub
			if (this.money > o.money) {
				return 1;
			} else if (this.money == o.money) {
				return o.value - this.value;
			}
			return -1;
		}
	}

	public static class minHeap2 implements Comparable<minHeap2> { // 성능순 정렬
		int num;
		int money;
		int value;

		public minHeap2(int num, int money, int value) {
			this.num = num;
			this.money = money;
			this.value = value;
		}

		@Override
		public int compareTo(minHeap2 o) {
			// TODO Auto-generated method stub
			return this.value - o.value;
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner(System.in);

		TC = sc.nextInt();

		for (int tc = 1; tc <= TC; tc++) {
			n = sc.nextInt();
			b = sc.nextInt();
			sum = 0;
			
			result = new PriorityQueue<minHeap2>();
			pcList = new ArrayList<PriorityQueue<minHeap>>();
			computer = new HashMap<String, Integer>();
			
			for (int i = 0; i < n; i++) {
				String pc = sc.nextToken(); // pc 종류
				sc.nextToken(); // 필요없는 정보(용량)
				int price = sc.nextInt(); // 가격
				int quality = sc.nextInt(); // 성능
				
				// 이미 list에 pc 부품이 있는 경우
				if (computer.get(pc) != null) {
					int num = computer.get(pc);
					pcList.get(num).add(new minHeap(num, price, quality));
				} else {
					// list에 pc 부품이 없는 경우 새로 생성
					int num = computer.size();
					computer.put(pc, num);
					pcList.add(new PriorityQueue<minHeap>());
					pcList.get(num).add(new minHeap(num, price, quality));
				}
			}

			
			// 초기 세팅 각 pclist에서 가장 낮은 값들을 가지고 전부 sum을 해서 계산시킨다.
			for (int i = 0; i < pcList.size(); i++) {
				minHeap next = pcList.get(i).poll();
				result.add(new minHeap2(next.num, next.money, next.value));
				sum += next.money;
			}
			
			algorithm();
			
			sc.write(resultvalue + "\n");
			
		}

		sc.close();

	}

	private static void algorithm() {
		while (true) {
			// 가장 낮은 부품 하나를 뺀다.
			minHeap2 product = result.poll();
			sum -= product.money;
			boolean flag = false;
			// 현재 pclist에가 비워질때까지 반복
			while (!pcList.get(product.num).isEmpty()) {
				// 현재 pclist의 부품에서 다음 수를 꺼낸다.
				minHeap next = pcList.get(product.num).poll();
				// 교체가 가능하다면 고체해서 추가한다.
				if (sum + next.money <= b && next.value > product.value) {
					sum += next.money;
					
					result.add(new minHeap2(next.num, next.money, next.value));
					flag = true;
					break;
				}
			}
			if (!flag) {
				// 교체할 부품이 없으면 끝낸다.
				resultvalue = product.value;
				return;
			}
		}
	}

	static class MyScanner {
		final BufferedReader reader;
		final BufferedWriter writer;
		static StringTokenizer tokenizer = null;

		MyScanner(InputStream in) {
			reader = new BufferedReader(new InputStreamReader(in));
			writer = new BufferedWriter(new OutputStreamWriter(System.out));
		}

		String nextToken() throws IOException {
			if (tokenizer == null || !tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}

			return tokenizer.nextToken();
		}

		int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(nextToken());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(nextToken());
		}

		void write(String sb) throws IOException {
			writer.write(sb);
		}

		void close() throws IOException {
			reader.close();
			writer.close();
		}
	}
}