알고리즘) 프로그래머스 BinarySearch, 예산

프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색)

예산

프로그래머스

(2020.04.24)

풀이1

이진 탐색(Binary Search)라는 생각없이 푼 풀이다. 사실 문제를 보고 이진 탐색을 써야지!! 이런 느낌이 안들어서 자연스럽게 푼 문제다.

로직은 아주 간단하다.

 

1. 예산의 액수에 따라 오름차순으로 도시를 정렬해준다.

2. 남은 예산으로 평균을 구했을 때 해당 도시의 예산 요청액이 더 적으면 허가해준다.

3. 만약, 요청한 예산이 남은 예산을 나눠줄 수 있는 금액보다 크다면 남은 총액으로 평균으로 상한선을 정한다. (정렬을 한 이유)

 

한 가지 더 생각해야할 점은 모든 도시의 요구 예산이 총 예산 안에 들어오면 answer는 0으로 변하지 않는다. 따라서, 이 경우에는 요청 예산안의 최대값을 return해준다.

 

풀이2

다음으로 게시할 문제인 입국심사 문제를 풀고나서 이진탐색 문제였다는 사실을 자각하고 다시 풀었다. 하지만 변수 핸들링에 꽤나 애를 먹어서 시간이 오래 걸렸다... ㅠㅠ

 

1. 요청한 예산안이 총 예산액에 들어오면 최대값을 return해준다. (이 때, 모든 예산을 더했을 때, 값이 int 범위를 넘어갈 수 있어서 변수타입을 long으로 만들어야한다.)

2. 상한선을 따로 정해야하는 경우라면 left와 right, mid를 통해 구한다. 모든 예산안을 검토하면서 상한선 mid를 넘어가는 예산은 mid로 더해서 총 예산액을 구한다. 주어진 예산보다 큰 경우는 최대 범위인 right의 값을 mid로 설정해준다. 예산보다 작거나 같을 경우는 예산 최저액인 left를 mid+1로 움직임을 반복하면서 예산을 구해준다. 또한, left와 right가 같은 값이 나온다면 해당 값에서 -1을 뺀 값을 입력하면서 추가적인 Breaking Point를 잡았다. (사실 문제의 답을 구하기 위해 추가한 검사인데, 왜인지는 아직도 모르겠다....)

 

---

 

(2020.06.05)

 

저번보다 어렵지 않게 푼 것 같다. 다만, 이분 탐색의 조건에서 left <right로 해줄 것인지 left<=right를 해줄 것인지에 따라 left와 right가 움직이는 값이 변해야한다. 그리고, left=right에서 답이 나올 경우 탐색을 할 수 없는 확률이 있기 때문에, left<=right를 해주는 것이 더 적절한 것같다. (프로그래머스 문제에 한에서는 그랬다.)

left<=right의 경우 조건에 따라, left = mid+1, right = mid-1로 움직여주면 된다.

 

그리고 이 문제에서 long으로 타입을 만들었었는데, 그러지 않아도 괜찮았다. 그래도 주어진 값이 애매하니까 long 타입으로 풀기는 했다. (이후에 int형으로 바꾸어 제출해봤는데, int형도 가능했다.)

 

코드 1

import java.util.Arrays;

public class KitBinarySearchBudget {
    private static int solution(int[] budgets, int M) {
        int answer = 0;

        Arrays.sort(budgets);
        for(int i=0; i< budgets.length; i++) {
            int avg = M/(budgets.length-i); // 남은 금액을 남은 도시로 나눈 평균
            if(budgets[i] >avg) {   // 책정된 예산이 avg보다 큰 경우
                answer = M/(budgets.length-i);  // 남은 금액으로 상한선 조정
                break;
            } else {
                M -= budgets[i];    // 예산 통과되는 도시의 예산을 빼줌
            }
        }

        return answer == 0 ? budgets[budgets.length-1] : answer;    // answer가 0이면 모든 예산이 통과되는 거니까 최대 예산 도시의 액수 리턴
    }

    public static void main(String[] args) {
        int[] budget = {1, 1, 1, 1, 1};
        int M = 5;

        System.out.println(solution(budget, M));
    }
}

코드 2

import java.util.Arrays;

public class KitBinarySearchBudget {
    private static int solution(int[] budgets, int M) { // 예산안 안에 들어오면 최대값 리턴, 아니면 이분 탐색
        Arrays.sort(budgets);
        return isInBudget(budgets,M) ? budgets[budgets.length-1] : binarySearch(budgets, M, budgets[budgets.length-1]);
    }

    private static boolean isInBudget(int[] budgets, int M) {
        long sum =0;
        for(int budget : budgets) {
            sum += budget;
        }
        return sum <= M ? true : false;
    }

    private static int binarySearch(int[] budgets, int M, int max) {
        int left =0;
        int right = max;

        while(left < right) {
            int mid = (left+right)/2;
            int total = getTotal(budgets, mid);     // 상한선을 mid로 더한 총 예산 구하기
            if(total > M) { // 주어진 예산보다 더 클 경우
                right = mid;    // 예산의 상한선 조정
            } else {    // 예산보다 작거나 같을 때
                left = mid+1;   // 하한선을 조정
            }

            if(left == right) { // 상한선과 하한선이 같을 때 left-1 리턴
                left -=1;
                break;
            }
        }

        return left;
    }

    private static int getTotal(int[] budgets, int mid) {
        int result =0;
        for(int budget : budgets) {
            result += budget > mid ? mid : budget;
        }
        return result;
    }

    public static void main(String[] args) {
//        int[] budget = {120, 110, 140, 150};
//        int M = 485;
        int[] budget = {120, 110, 140, 150, 500};
        int M = 685;
//        int[] budget = {1, 1, 1, 1};
//        int M = 4;
//        int[] budget = {120, 110, 140, 150};
//        int M = 4000;

        System.out.println(solution(budget, M));
    }
}

 

코드 2

 

import java.util.Arrays;

class Solution {
    public int solution(int[] budgets, int M) {
        return binarySearch(budgets,M);
    }
    
    private int binarySearch(int[] budgets, int M) {
        int result =0;
        Arrays.sort(budgets);
        int left = 1;
        int right = budgets[budgets.length-1];
        
        while(left <= right) {
            int mid = (left+right)/2;
            if(isInTotal(budgets,M,mid)) {  // 예산 통과 가능
                result =mid;
                left = mid+1;
            } else { // 불가능
                right =mid-1;
            }
        }
        return result;
    }
    
    private boolean isInTotal(int[] budgets, int M, int limit) {
        long sum =0;
        for(int num : budgets) {
            if(num > limit) {
                sum += limit;
            } else {
                sum += num;
            }
        }
        return sum <=M ? true : false;
    }
}