(Java) 백준 2512번

백준 2512번 실버2 정답률 35.131%

문제

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int totalNum = Integer.parseInt(br.readLine());
		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str, " ");
		int sum = 0;
		int max = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i = 0; i < totalNum; i++) {
			int num = Integer.parseInt(st.nextToken());
			max = max > num? max : num;
			sum += num;
            if(map.containsKey(num)) map.put(num, map.get(num) + 1);
			else map.put(num, 1);
		}
		List<Integer> sortedList = map.entrySet().stream().sorted(Comparator.comparing(Map.Entry::getKey, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return o2 - o1;
			}
		}))
		.map(Map.Entry::getKey)
	    .collect(Collectors.toList());
		int totalValue = Integer.parseInt(br.readLine());
		int differTotal = sum - totalValue;
		if(differTotal <= 0) bw.write(max + "");
		else {
			int minusNum = 0;
			int i = 0;
			for(int a : sortedList) {
				minusNum += map.get(a);
				int afterNum;
				if(sortedList.size() == i + 1) afterNum = 0;
				else afterNum = sortedList.get(i + 1);
				int differ = a - afterNum;
				if(sum - differ * minusNum <= totalValue) {
					bw.write((int)(a - Math.ceil((sum - totalValue) / (double) minusNum)) + "");
					break;
				}
				if(i == sortedList.size() - 1) {
					bw.write("0");
					break;
				}
				sum -= differ * minusNum;
				i++;
			}
		}
		bw.flush();
        br.close();
        bw.close();
	}

}

(1) 주어진 숫자를 순회하면서 max값, sum값, Map에 Key : 숫자, Value : 개수 로 저장합니다.

(2) Key를 내림차순으로 정렬한 List를 만듭니다.

(3) 만약 주어진 합계보다 sum값이 작다면 모든 예산이 통과되므로 max값을 출력합니다.

(4) 만약 주어진 합계보다 sum값이 큰 경우 Key를 내림차순으로 정렬한 List를 순회하면서 (다음 요소와의 차이 * 감소대상인 요소의 개수) 보다  (주어진 합계 - sum) 값이 작은 경우 이 부분에서 예산 max값을 계산합니다.

(5) (다음 요소와의 차이 * 감소대상인 요소의 개수) 보다  (주어진 합계 - sum) 값이 큰 경우 이번 요소의 최소값을 sum에 계산해주고(다음 요소의 최대값) 다음 요소로 진행해 절차를 반복합니다.

(6) 만약 마지막 요소라면 다음 요소를 0으로 가정해 (현재 요소 - 다음 요소) 차이를 계산하고 마지막 요소인데도 (다음 요소와의 차이 * 감소대상인 요소의 개수) 보다  (주어진 합계 - sum) 값이 큰 경우 주어진 합계가 0보다 작은 값이 주어진 상황이므로 0을 출력합니다.

 

이상입니다. 지금까지 읽어주셔서 감사합니다.