Lv.2? [이진 탐색] - 예산(kit 전용 문제)

---

[ 문제 링크 ]

프로그래머스 Lv2?. 예산

 
[ 문제 설명 이미지 ]

 

 

예산

각 지방에서 신청한 예산안 들이 있는데, 국가의 총 예산을 넘지 않는 선에서 수용 가능한 최대 상한가를 구하라는 문제이다.
예산의 상한가가 정해지면, 요청된 예산이 상한가보다 크거나 같을 경우 상한가 만큼만 지급하고, 상한값보다 작으면 신청된 예산값만 지급한다.

각 지방에서 신청한 예산 액이 있고, 이 예산액의 총 합이 국가에서 지정한 총예산값을 넘기면 안된다.
특정 상한값을 정하고 상한값보다 큰 경우 상한값 만큼만 제공한다.
상한값을 찾아내는것이 문제의 핵심이다.

이진탐색

주어진 데이터에서 내가 원하는 특정 데이터를 찾아내는것을 `탐색` 이라고 한다.

가장 단순한 방법은 모든 경우의 수 0에서부터 최대값 사이를 모두 순회하며 탐색하는것이다.
그러나 이런 방식은 시간이 너무 오래걸린다.
이 문제에서 찾는 값은 최소값0과 최대값150 으로 주어져있다.
가장 낮은금액 0 ~ 가장 높은금액 150은 정렬 되어있는 상태이므로 이진탐색을 적용할 수 있게 된다.

이진탐색은 1과 150 사이의 전체 데이터를 모두 다 확인하지 않고 범위를 줄여가며 탐색을 한다.

최소값과 최대값 사이의 어딘가 쯤에 내가 원하는 상한가가 있을 것이므로 
1~150이라는 범위에 대한 중간값을 취한 후 각 지역별 상한가가 성립되는지 확인한다.
중간값을 상한값으로 지정했을 때 루프를 돌려 선택된 지역의 예산액이 상한값보다 클 경우 `상한값`을 누적으로 더한다.
만약 예산이 상향값과 같거나 작을 경우 `예산값`을 누적으로 더한다.
(각 지역별 상한액 혹은 요청예산액을 더하는것임.)

누적 상한값 총 합이 현재 전체 예산을 초과했는지 확인한다.
ㄴ만약 초과하지 않았다면 상향조정하고 임시 상한가를 갱신한다.
상한값은 중간값부터 최대값 사이의 값을 갖게 된다.
ㄴ 만약 초과한다면 하향조정한다.
하한값은 최소값부터 중간값 사이의 값을 갖게 된다.

이런식으로 최대값과 최소값이 수렴할(같아질) 때 까지 반복해서 누적값을 구하고 누적값과 총예산을 비교하며 상/하향 조정을 한다.

---

[풀이 1] 

class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int min = 0;
        int max = 0;

        for (int budget : budgets) {
            if(budget > max) max = budget; // 만약 최대값보다 지역예산이 크다면, 지역예산을 최대값으로 선택한다.
        }

        while(min <= max) {
            int mid = (min + max)/2; //중간값 상한액
            int sum = 0;

            // 각 지역별 예산에 대한 상한액의 누적합을 연산한다.
            for (int budget : budgets) {
                if(budget > mid) sum += mid; // 예산이 상한값보다 클 경우 상한값을 누적.
                else sum+= budget; // 예산이 상한값과 같거나 작을경우 예산값을 누적한다.
            }

            if(sum <= M) { // 총 합이 총 예산보다 작다면 상향조정 해야한다.
                min = mid + 1; // [상향조정] 1 2 일 경우 상한액이 1 인데 그걸 다시 mid
                answer = mid; // 답 갱신
            } else { //총 합이 총 예산보다 작으면 하향조정 해야한다.
                max = mid - 1; // [하향조정]
            }
        }
        return answer;
    }
}

 

풀이과정

최소값을 0으로 지정하고 요청한 지역별 예산액들 중 최대값(150)을 구한다.

 

최소값이 최대값보다 같거나 커지기 전 까지 중간값인 상한액을 구하는 과정을 반복한다.

각 지역별 예산에 대한 상한액의 누적합을 연산한다.

 

먼저 중간값인 상한액을 (최소값 + 최대값)/2 로 구한다 ((0+150) /2 = 75)

 

각 지역별 요청 예산을 기준으로 제공될 예산값에 대한 누적합을 연산한다.

요청액이 상한액 보다 클 경우 상한액 보다 큰 값을 제공할 수 없으므로 일단 상한액을 누적한다.

요청액이 상한액 보다 같거나 작을 경우 상한액 미만이므로 현재 예산을 누적한다.

 

이윽고, 각 지역별 요청 예산 기준 제공될 예산값에 대한 누적합 연산이 끝날경우 해당 총 예산합 금액과 제공될 수 있는 총 예산을 비교한다.

 

지역별 요청 총 예산합이 제공가능한 총 예산값 보다 작거나 같을 경우 상한액을 더 높일 수 있으므로 `상향 조정`해야 한다.

이진탐색에서 `상향조정`은 중간값과 최대값 사이 값을 구해야 하므로 최소값에 중간값 + 1을 저장한다.

(최소값을 중간값으로 증가함으로써 원래 최소~최대이지만 중간~최대 에서 탐색하게된다)

반복 조건이 최대값이 최소값보다 크거나 같을 때 까지만 돌기 때문에, 최소값이 최대값보다 크거나 같아질 경우 반복되지  않으므로 상한액을 답에 미리 갱신해 놓는다.

(최소값을 값 갱신전에 먼저 저장 했으므로 다음 loop를 돌아야 하는지 while조건에서 최대값보다 크거나 같아졌는지 한번 더 검증하기 때문)

 

지역별 총 예산합이 제공가능한 총 예산값보다 클 경우 지급범위의 예산값을 초과하였으므로 상한액을낮춰야 한다. 따라서 `하향조정` 해야 한다.

이진탐색에서 `하향조정`은 최소값과 중간값 사이의 값을 구해야 하므로 최대값에 중간값 - 1을 저장한다.

(최대값을 중간값으로 감소함으로써 원래 최소~최대이지만 최소~중간 에서 탐색하게된다)

 

총 예산합이 제공가능한 총 예산값보다 클 경우 반복문이 더이상 실행되지 않으므로 반복문이 종료되고 바로 직전 상향 조정시 갱신해 뒀던 답을 반환하게 된다.

실제 디버깅

총 예산액 485 / 지역별 요청액 [120, 110, 140, 150] 

 

최소값 <= 최대값 (0<= 150) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (0+150)/2 = 75 (최초) 

중간값 75가 요청액 120보다 크지 않으므로 일단 누적 => 75를 누적 75

중간값 75가 요청액 110보다 크지 않으므로 일단 누적 => 75을 누적 150

중간값 75가 요청액 140보다 크지 않으므로 일단 누적 => 75을 누적 225

중간값 75가 요청액 150보다 크지 않으므로 일단 누적 => 75을 누적 300

 - 300은 총 예산액인 485보다 작으므로 예산범위에 포함되기 때문에 최소값에 중간값+1인 76으로 `상향조정`

 

최소값 <= 최대값 (76 <= 150) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (76+150)/2 = 113

중간값 113이 요청액 120보다 크지 않으므로 일단 누적 => 113을 누적 113

중간값 113이 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 223

중간값 113이 요청액 140보다 크지 않으므로 일단 누적 => 113을 누적 336

중간값 113이 요청액 150보다 크지 않으므로 일단 누적 => 113을 누적 449

- 449는 총 예산액인 485보다 작으므로 예산범위에 포함되기 때문에 최소값에 중간값+1인 114로 `상향조정`

 

최소값 <= 최대값 (114<= 150) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (114+150)/2 = 132

중간값 132가 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 132가 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 132가 요청액 140보다 크지 않으므로 일단 누적 => 132를 누적 362

중간값 132가 요청액 150보다 크지 않으므로 일단 누적 => 132를 누적 494

- 494는 총 예산액인 485보다 크므로 예산범위에 포함되지 않기 때문에 최대값에 중간값-1인 131로 `하향조정`

 

최소값 <= 최대값 (114 <= 131) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (114+131)/2 = 122

중간값 122가 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 122가 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 122가 요청액 140보다 크지 않으므로 일단 누적 => 122를 누적 352

중간값 122가 요청액 150보다 크지 않으므로 일단 누적 => 122를 누적 474

- 474는 총 예산액인 485보다 작으므로 예산범위에 포함되기 때문에 최소값에 중간값+1인 123으로 `상향조정`

 

최소값 <= 최대값 (123 <= 131) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (123+131)/2 = 127

중간값 127이 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 127이 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 127이 요청액 140보다 크지 않으므로 일단 누적 => 127을 누적 357

중간값 127이 요청액 150보다 크지 않으므로 일단 누적 => 127을 누적 484

- 484는 총 예산액인 485보다 작으므로 예산범위에 포함되기 때문에 최소값에 중간값+1인 128로 `상향조정`

- 답 127로 일단 갱신

 

최소값 <= 최대값 (128 <= 131) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (128+131)/2 = 124

중간값 124가 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 124가 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 124가 요청액 140보다 크지 않으므로 일단 누적 => 129를 누적 359

중간값 124가 요청액 150보다 크지 않으므로 일단 누적 => 129를 누적 488

- 488는 총 예산액인 485보다 크므로 예산범위에 포함되지 않기 때문에 최대값에 중간값-1인 129로 `하향조정`

 

최소값 <= 최대값 (128 <= 129) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (128+130)/2 = 129

중간값 129이 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 129이 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 129이 요청액 140보다 크지 않으므로 일단 누적 => 129를 누적 359

중간값 129이 요청액 150보다 크지 않으므로 일단 누적 => 129를 누적 488

- 488는 총 예산액인 485보다 크므로 예산범위에 포함되지 않기 때문에 최대값에 중간값-1인 128으로 `하향조정`

 

최소값 <= 최대값 (128 <= 128) 참 이므로 루프를 돈다.

중간값 = (최소값+최대값)/2 => (128+128)/2 = 128

중간값 128이 요청액 120보다 크므로 지급가능 요청액 누적 => 120을 누적 120

중간값 128이 요청액 110보다 크므로 지급가능 요청액 누적 => 110을 누적 230

중간값 128이 요청액 140보다 크지 않으므로 일단 누적 => 128을 누적 358

중간값 128이 요청액 150보다 크지 않으므로 일단 누적 => 128을 누적 486

- 486는 총 예산액인 485보다 크므로 예산범위에 포함되지 않기 때문에 최대값에 중간값-1인 127으로 `하향조정`

 

최소값 <= 최대값 (128 <= 127) 거짓 이므로 루프를 돈다.

최종 갱신값으로 가장 마지막에 저장된 상향조정 값 127을 반환한다

상향조정시 +1 하향조정시 -1 하는 이유

예를들어 최대값 2와 최소값8 이라고 했을 때 4를 찾는다
중간값은 5 이고 4가 되려면 작아야 하므로 최대값을 5로 줄인다
그럼 2와 5가 된다.
다시 4를 찾는다
중간값은 3이고 4가되려면 커져야 하므로 최소값을 3으로 늘린다.
그럼 3과 5가 된다.
다시 4를 찾는다.
중간값은 4이다.

1, 2 같은경우 때문에 1을 증가시킨다.
1과 2 사이에서 1은 찾을 수 있지만 2는 찾을 수 없다.
왜냐면 이 연산은 소수점아래로 버림 하기때문이다.

만약 2와 8에서 4를 찾을때 최소값, 최대값에서 1을 더하고 뺀다고 생각해보자
중간값은 5가 되고 4가 되려면 작아야 하므로 최대값을 5로 줄인다. 이때 1을 더 줄여보자.
그럼 2와 4가 된다.
다시 4를 찾는다.
중간값은 3이고 4가 되려면 커져야 하므로 최소값을 3으로 늘린다. 이때 1을 더 늘려보자.
그럼 4와 4가 된다.
중간값은 4이다.

어떤 규칙성이라고 아직 설명을 풀어서 못하겠다.

 

---

[풀이 2] Stream처리 : 최대값 연산 및 각 지역별 예산에 대한 상한액의 누적합 

 

import java.util.stream.IntStream;

public class Refactor {


    public int solution(int[] budgets, int M) {
        int answer = 0;
        int min = 0;
        int max = IntStream.of(budgets).max().getAsInt();

        for (int budget : budgets) {
            if(budget > max) max = budget; // 만약 최대값보다 지역예산이 크다면, 지역예산을 최대값으로 선택한다.
        }

        while(min <= max) {
            final int mid = (min + max)/2; //중간값 상한액 - stream사용시 가변 변수를 사용하면 안되므로 final변수로 선언해야 한다.

            // 각 지역별 예산에 대한 상한액의 누적합을 연산한다.
            int sum = IntStream.of(budgets)
                    .map(budget -> Math.min(budget, mid)) // 예산값과 상한값 중 최소값을 누적으로 더한다.
                    .sum();

            if(sum <= M) { // 총 합이 총 예산보다 작다면 상향조정 해야한다.
                min = mid + 1; // [상향조정] 1 2 일 경우 상한액이 1 인데 그걸 다시 mid
                answer = mid; // 답 갱신
            } else { //총 합이 총 예산보다 작으면 하향조정 해야한다.
                max = mid - 1; // [하향조정]
            }
        }
        return answer;
    }

}

 

---

[나의 풀이] 오답1 (단순 계산)

class Solution {
    public int solution(int[] budgets, int M) {
        int avg = M / budgets.length;
        int temp = 0;
        int count = 0;
        for (int budget : budgets){
            if(avg > budget) temp += avg-budget;
            if(avg < budget) count++;
        }
        return avg + temp/count;
    }
}

 

 

[나의 풀이] 오답2 (이진탐색 적용)

package programmers.kit.part03_binarySearch;

public class Solution {

    public int solution(int[] budgets, int M) {
        int answer = 0;
        int min = 1;
        for (int budget : budgets) {
            int max = budget;
            int mid = (min+max)/2;
            while (min < mid) {
                mid = (min+max)/2;
                if (mid * budgets.length < M ) { //485
                    min = mid;
                    if(min == max) {
                        answer += mid;
                        break;
                    }
                    continue;
                }
                if(mid * budgets.length > M ) {
                    max = mid;
                }
            }
        }
        return answer;
    }

}

 
내가 잘못 푼건, mid값 상한액에 대해서 각 지역의 예산과 비교한 뒤에 누적으로 더하고 그 누적합을 총 예산액과 비교했어야 했는데,
mid값을 배열의 예산의 갯수만큼 반복해서 누적으로 더했기 때문에
기준점이 바뀌지 않아 최적값을 찾지 못하고 틀렸던 것이다.
 

75+150/2 = 225/2 = 75 < 112 < 150 -> 448 < 485 커야함
112+150/2 = 262/2 = 112 < 131 < 150 -> 524 > 485 작아야함
112+131/2 = 243/2 = 112 < 121 < 131 -> 484 < 485 커야함
121+131/2 = 252/2 = 121 < 126 < 131 -> 504 > 485 작아야함
121+126/2 = 247/2 = 121 < 123 < 126 -> 492 > 485 작야아함
121+123/2 = 244/2 = 121 < 122 < 123 -> 488 > 485 작아야함
121+122/2 = 243/2 = 121 < 121 < 122 -> 484 > 485 커야함
121+122/2 = 242/2 = 121 < 121 < 121 -> 같음

 

121.... 127이 나와야함..