백준 3691 <컴퓨터 조립>

 

골드 5라는 난이도를 믿지 못할 문제의 난이도였던 문제이다.

 

이 문제는 모든 부품의 종류를 선택하는데 선택햇던 부품 중 가장 낮은 성능을 올려주는 것을 최우선으로 한다.

 

교체를 할때에는 가격이 낮은 순으로 성능이 좋은 것을 교체해준다.

 

풀이 방법

1. 각 부품을 hashmap에 제품의 이름을 key로 arraylist에 저장할 위치번호를 value로 저장한다.
2. arraylist의 속성을 우선순위 큐로 해서 각각의 부품을 가격순으로 정렬한다.
3. 모든 부품을 선택하기 위해 각각의 arraylist에 꺼내어 새로운 우선순위 큐에 저장한다. 
   1. 이때는 성능이 낮은 부품을 꺼내야 하기 때문에 성능 순으로 정렬되게 한다.
4. 성능이 낮은 부품을 꺼내 해당 부품에서 가격이 낮고 자신보다 성능이 높은 것이 나올 때까지 진행한다.
5. 성능이 높은 것이 존재하지 않으면 현재 낮은 것을 결과로 저장한다.

 

 

시작을 하기 위한 세팅!

 

가격이 가장 작은 부품들을 result에 넣어준다.

result에서 성능이 가장 작은 부품을 꺼내 다른 부품 중 가격이 낮고 성능이 좋은 것을 선택

 

없다면 flag는 false일 테고 그러면 그 값을 출력한다.

 

생각할 것이 많았던 골드 5문제. 많은 생각을 요하고 자료구조의 사용을 알아야 풀 수 있는 문제였다.

 

전체 코드

 

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

public class Main {

	public static class min implements Comparable<min> {
		int num;
		int money;
		int value;

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

		@Override
		public int compareTo(min 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 min2 implements Comparable<min2> {
		int num;
		int money;
		int value;

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

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

	static HashMap<String, Integer> hm;//
	static ArrayList<PriorityQueue<min>> a;// 순서대로 담을 거
	static PriorityQueue<min2> result; //가치가 작은걸 뺄거다.
	static int t, n, b,sum,resultvalue;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		t = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= t; tc++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			n=Integer.parseInt(st.nextToken());
			b=Integer.parseInt(st.nextToken());
			sum=0;
			result=new PriorityQueue<min2>();
			a = new ArrayList<PriorityQueue<min>>();
			hm = new HashMap<String, Integer>();
			for(int i=0;i<n;i++) {
				st=new StringTokenizer(br.readLine());
				String pc=st.nextToken();
				st.nextToken();
				int price=Integer.parseInt(st.nextToken());
				int v=Integer.parseInt(st.nextToken());
				if(hm.get(pc)!=null) {
					int num=hm.get(pc);
					a.get(num).add(new min(num,price,v));
				}
				else {
					int num=hm.size();
					hm.put(pc,num);
					a.add(new PriorityQueue<min>());
					a.get(num).add(new min(num,price,v));
				}
			}//다 분류 완료
			
			init();
			start();
			System.out.println(resultvalue);
		}
		
	}

	private static void start() {
		// TODO Auto-generated method stub
		while(true) {
			min2 remo=result.remove();
			sum-=remo.money;
			boolean flag=false;
			while(!a.get(remo.num).isEmpty()) {
				min next=a.get(remo.num).remove();
				if(sum+next.money<=b&&next.value>remo.value) {
					sum+=next.money;
					result.add(new min2(next.num,next.money,next.value));
					flag=true;
					break;
				}
			}
			if(!flag) {
				resultvalue=remo.value;
				return;
			}
		}
	}

	private static void init() {
		// TODO Auto-generated method stub
		for(int i=0;i<a.size();i++) {
			min next=a.get(i).remove();
			result.add(new min2(next.num,next.money,next.value));
			sum+=next.money;
		}
		
	}

}