[프로그래머스] 예산 - java

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int max = 0;
        for (int i = 0; i < budgets.length; i++) {
			max = Math.max(budgets[i], max);
		}     
        int first = 0;
        int end = max;

        while(true){
            long result=0;
            if(first>end){
                break;
            }
            int middle = (first+end)/2;
            for(int i = 0 ; i<budgets.length; i++){
                if(budgets[i]>middle){
                    result+=middle;
                }
                else{
                    result+=budgets[i];
                }
            }
            if(result>M){
                end=middle-1;
            }
            else{
                first=middle+1;
                answer = Math.max(answer, middle);
            }
        }
        return answer;
    }
}

 

 

 

<사고과정>

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int sum=0;
        for(int i =0; i<budgets.length; i++){ //처음의 예산 총 합
            sum+=budgets[i];
        }
        if(sum<M){//예산 총 합이 국가예산 보다 작을 때 상한액은 요청된 예산의 최댓값
            int max =0 ;
            for(int i =0; i<budgets.length; i++){
                if(max<budgets[i]){
                    max=budgets[i];
                }
            }
            answer=max;
        }
        else{ //요청된 예산 총 합이 국가예산보다 클 때 상한액을 찾아감
            List<Integer> list = new ArrayList<Integer>();
            for(int i =0; i<budgets.length; i++){
                list.add(budgets[i]);
            }
            Collections.sort(list);//list sort
            int first = list.get(1);
            int end = list.get(list.size()-1);
            
            while(true){
                int result=0;
                if(first>end){
                    break;
                }
                int middle = (first+end)/2;
                for(int i = 0 ; i<list.size(); i++){
                    if(list.get(i)>middle){
                        result+=middle;
                    }
                    else{
                        result+=list.get(i);
                    }
                }
                if(result>M){
                    end=middle-1;
                }
                else{
                    first=middle+1;
                    answer=middle;
                }
            }
        }
        return answer;
    }
}

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int sum=0;
        for(int i =0; i<budgets.length; i++){ //처음의 예산 총 합
            sum+=budgets[i];
        }
        if(sum<M){//예산 총 합이 국가예산 보다 작을 때 상한액은 요청된 예산의 최댓값
            int max =0 ;
            for(int i =0; i<budgets.length; i++){
                if(max<budgets[i]){
                    max=budgets[i];
                }
            }
            answer=max;
        }
        else{ //요청된 예산 총 합이 국가예산보다 클 때 상한액을 찾아감
            List<Integer> list = new ArrayList<Integer>();
            for(int i =0; i<budgets.length; i++){
                list.add(budgets[i]);
            }
            Collections.sort(list);//list sort
            int first = list.get(1);
            int end = list.get(list.size()-1);
            
            while(true){
                int result=0;
                if(first>end){
                    break;
                }
                int middle = (first+end)/2;
                for(int i = 0 ; i<list.size(); i++){
                    if(list.get(i)>middle){
                        result+=middle;
                    }
                    else{
                        result+=list.get(i);
                    }
                }
                System.out.println("result : "+result);
                if(result>M){
                    
                }
                else{
                    
                }
            }
        }
        return answer;
    }
}

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int sum=0;
        for(int i =0; i<budgets.length; i++){ //처음의 예산 총 합
            sum+=budgets[i];
        }
        if(sum<M){//예산 총 합이 국가예산 보다 작을 때 상한액은 요청된 예산의 최댓값
            int max =0 ;
            for(int i =0; i<budgets.length; i++){
                if(max<budgets[i]){
                    max=budgets[i];
                }
            }
            answer=max;
        }
        else{ //요청된 예산 총 합이 국가예산보다 클 때 상한액을 찾아감
            List<Integer> list = new ArrayList<Integer>();
            for(int i =0; i<budgets.length; i++){
                list.add(budgets[i]);
            }
            Collections.sort(list);//list sort
            
            int middle = (list.get(1)+list.get(list.size()-1))/2;
            while(true){
                int result;
                for(int i = 0 ; i<list.size(); i++){
                    if(list.get(i)>middle){
                        result+=middle;
                    }
                    else{
                        result+=list.get(i);
                    }
                }
                if(result>M){
                    middle--;
                }
            }
        }
        return answer;
    }
}

class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int sum=0;
        for(int i =0; i<budgets.length; i++){ //처음의 예산 총 합
            sum+=budgets[i];
        }
        if(sum<M){//예산 총 합이 최대치보다 작을 때 max 값은 요청된 예산의 최댓값
            int max =0 ;
            for(int i =0; i<budgets.length; i++){
                if(max<budgets[i]){
                    max=budgets[i];
                }
            }
            answer=max;
        }
        else{
            
        }
        return answer;
    }
}