[백준] 25045번: 비즈마켓 Java

문제

비즈마켓은 "고객 기업 운영의 효율화에 기여하며, 그 구성원의 복지 만세를 추구한다." 라는 기조 아래 기업을 주 대상으로 복지몰 사업, 기업 판촉 및 사은품 사업, 산업재 유통 사업을 하는 온라인 종합상사입니다. 이 주 사업 분야 외에도 비즈마켓은 브랜드 사업, 렌탈 사업, 에너지 사업 등 다양한 분야에서 사업을 진행하고 있습니다. 오늘 신욱이는 비즈마켓으로부터 효율적으로 렌탈 사업을 운영하는 것을 도와달라는 의뢰를 받았습니다.

비즈마켓에는 N개의 물품이 있고, 물품을 렌탈하기를 원하는 M개의 고객 기업이 있습니다. 각 물품은 Ai 의 만족도를 가지고 있으며, 각 고객 기업은 Bj 의 비용을 지불하여 렌탈을 진행하고자 합니다. 각 고객 기업은 하나의 물품만 렌탈할 수 있으며, 각 물품 또한 하나의 고객 기업에만 렌탈해줄 수 있습니다.

 Ai의 만족도를 가지는 물품을 Bj 의 비용을 지불하고자 하는 고객 기업에 렌탈해주게 되면 Ai−Bj만큼의 고객 만족도를 얻을 수 있습니다. 모든 고객 기업들은 적어도 자신이 지불한 비용만큼의 만족도를 얻기를 원하기 때문에, 고객 만족도가 0보다 작아진다면 거래를 진행하지 않을 것입니다. 거래를 진행하지 않으면 당연히 고객 만족도도 얻을 수 없습니다.

신욱이가 구체적으로 해야 하는 일은 각 고객 기업에 렌탈해 줄 물품을 잘 정해서 고객 만족도의 합을 최대로 만드는 것입니다. 하지만 신욱이는 해야 할 과제가 너무 많았던 나머지, 이 일을 여러분들한테 넘기고 과제를 하러 떠나버렸습니다. 신욱이를 대신해 고객 만족도의 합의 최댓값을 구해줍시다.

 

입력

첫 번째 줄에는 상품의 수를 의미하는 정수 N과 고객 기업의 수를 의미하는 정수 M이 공백으로 구분되어 주어집니다. (1≤N,M≤2×10^5)

두 번째 줄에는 각 상품의 만족도 A1,A2,A3,…,A_N 을 의미하는 정수 N개가 공백으로 구분되어 주어집니다. (0≤Ai≤10^9)

세 번째 줄에는 고객 기업이 지불하고자 하는 비용 B1,B2,B3,…,B_M을 의미하는 정수 M개가 공백으로 구분되어 주어집니다. (0≤Bj≤10^9)

 

출력

첫 번째 줄에 각 고객 기업에 대여해 줄 물품을 잘 골라서 얻을 수 있는 고객 만족도의 합의 최댓값을 출력합니다.

 

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

25045번: 비즈마켓

 

접근

그리디 알고리즘으로 해결할 수 있습니다.

고객만족도의 합의 최댓값을 출력해야 함으로

불합리하지만 가장 적은 비용을 지불한 기업에 가장 높은 만족도 상품을 제공합니다.

 

상품 만족도는 높은순 정렬, 고객 지불 비용은 낮은순으로 정렬한 뒤 매칭시킵니다.

이 때, 상품 만족도가 고객 지불 비용보다 낮다면

다음 차례의 고객도 같은 문제를 가지기에 만족도 계산을 멈춥니다.

 

여기서는 정렬을 위해 우선순위 큐를 사용하였습니다.

 

구현

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

public class 비즈마켓 {
	//https://www.acmicpc.net/problem/25045
	//내림차순 정렬
	static class DescendOrder implements Comparator<Long>{
		@Override
		public int compare(Long o1, Long o2) {
			if(o1<o2) return 1;
			else if(o1>o2) return -1;
			return 0;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()); //상품 수
		int m=Integer.parseInt(st.nextToken()); //고객 수
		//상품의 만족도가 높은 순 poll 되는 pq
		PriorityQueue<Long> productsPq = new PriorityQueue<>(new DescendOrder());
		//고객 지불 비용이 낮을 수록 poll 되는 pq
		PriorityQueue<Long> clientsPq = new PriorityQueue<>();
		//상품 만족도 입력
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			productsPq.add(Long.parseLong(st.nextToken()));
		}
		//고객 지불 비용 입력
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<m;i++) {
			clientsPq.add(Long.parseLong(st.nextToken()));
		}
		
		long answer = 0;
		//두 pq중 하나라도 빌때 까지 반복
		while(!clientsPq.isEmpty()&&!productsPq.isEmpty()) {
			long product = productsPq.poll();
			long client = clientsPq.poll();
			//상품 만족도가 고객 지불 비용 보다 못하면 stop
			//(다음 상품 만족도는 더 낮아지고, 다음 고객 비용은 높아짐)
			if(product<client) {
				break;
			}
            //만족도의 합
			answer+=(product-client);
		}
		//출력
		System.out.println(answer);
		
		br.close();
	}
}