예산

https://programmers.co.kr/learn/courses/30/lessons/43237

budgets를 Vector에 넣어주고, Vector를 정렬해주는 방식(Collections.sort())으로 구현했다가 효율성에서 시간 초과가 발생했다.

그래서, 그냥 Arrays.sort()를 사용했다.

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
 
    static boolean chk(int[] budgets, int M, int mid)
    {
        int sum = 0, len = budgets.length;
        
        for(int i=0; i<len; i++) {
            if(budgets[i] > mid) {
                sum += mid;
            }
            else {
                sum += budgets[i];
            }
        }
        
        return sum <= M;
    }
    
    static int solution(int[] budgets, int M) {
        int answer = 0, len = budgets.length, sum = 0, Left = 0, Right = 0;
        
        Arrays.sort(budgets);
        Right = budgets[len - 1];
                
        while(Left <= Right) {
            int mid = (Left + Right) >> 1;
        
            if(chk(budgets, M, mid)) {
                answer = Math.max(answer, mid);
                Left = mid + 1;
            }
            else {
                Right = mid - 1;
            }
        }
        
        return answer;
    }
    
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //st = new StringTokenizer(br.readLine());
 
        int[] budgets = { 120, 110, 140, 150 };
        int M = 485;
        
        System.out.println(solution(budgets, M));
            
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second;
    
    PQ(int f, int s) {
        this.first = f;
        this.second = s;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}