since 2019.

4 minute read

Updated:

문제 설명

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

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

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다.각 지방에서 요청하는 예산이 담긴 배열 budgets과 총 예산 M이 매개변수로 주어질 때, 위의 조건을 모두 만족하는 상한액을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • 지방의 수는 3 이상 100,000 이하인 자연수입니다.
  • 각 지방에서 요청하는 예산은 1 이상 100,000 이하인 자연수입니다.
  • 총 예산은 지방의 수 이상 1,000,000,000 이하인 자연수입니다.

입출력 예

budgets M return
[120, 110, 140, 150] 485 127

구현 과정

  1. 최소값은 0으로 선언하고, 예산이 담긴 배열 budgets을 오름차순으로 정렬하여 최대값을 구한다.
  2. 중간값(mid)을 구하고, 배열 각각의 값이 총 예산(M)을 넘지 않으면 배열 값을 합계에 더하고, M을 넘으면 M값을 합계에 더한다.
  3. 중간값(mid)을 상한액으로 한 합계가 총 예산(M)을 넘지 않으면, 최소값을 중간값 + 1 높여 확인한다. 이때, 일단은 예산을 넘지 않으므로 중간값을 answer에 저장해둔다. 반대로 합계가 총 예산(M)을 넘으면, 최대값을 중간값 -1 낮춰 확인한다.
  4. 2-4의 과정은 최소값이 최대값보다 커지기 전까지 반복한다.

구현 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int min = 0;
        int max = budgets[0]; //최대값 초기값 셋팅

				//budgets을 오름차순으로 정렬하고 최대값 구하기
        Arrays.sort(budgets);

        for (int i = 1; i < budgets.length; i++) {
            if (budgets[i] > max) {
                max = budgets[i];
            }
        }

				//최소값이 최대값보다 작을 때까지 반복한다.
        while (min <= max) {
						//중간값 구하기
            int mid = (max + min) / 2;

            int sum = 0; // 합계 초기화

						//중간값으로 한 budgets의 합계 구하기
            for (int i = 0; i < budgets.length; i++) {
                if (mid < budgets[i]) sum += mid;
								else sum += budgets[i];
            }

            if(sum <= M){ // 총합이 예산 M을 넘지 않는 경우, 최소값을 +1 높여 확인한다.  
                answer = mid; //조건에 충족하므로 값을 일단 저장함.
                min = mid + 1;
            } else if(sum > M){ // 총합이 예산 M을 넘는 경우, 최대값을 -1 낮춰 확인한다.
                max = mid - 1;
            }
        }
        return answer;
    }
}

리팩토링 1

  • max 값을 찾는 반복문 대신에 Arrays 클래스의 max 메소드를 이용하여 최대값을 찾는다.
  • 속도가 느려서 확인해보니, 오름차순 정렬은 불필요하다. 배열값을 찾는 게 아니라, 합계를 가지고 범위를 좁히기 때문.
  • 반복문에서 배열의 크기를 가져오는 대신 for-each문을 사용했다.
import java.util.Arrays;

class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int start = 0;
        int end = Arrays.stream(budgets).max().orElse(0); //max 값을 찾는 반복문 대신에 Arrays 클래스의 max 메소드를 이용하여 최대값을 찾는다. 
        int len = budgets.length;

//      Arrays.sort(budgets);
//
//      for (int i = 1; i < budgets.length; i++) { //정렬은 불필요. 배열값을 찾는 게 아니라, 합계를 가지고 범위를 좁히기 때문.
//          if (budgets[i] > max) {
//              max = budgets[i];
//          }
//      }

        while (start <= end) {
            int mid = (end + start) / 2;

            long sum = 0;

						for(int budget : budgets) { //반복문에서 배열의 크기를 가져오는 대신 for-each문을 사용함.
                if (budget > mid) sum += mid;
                else sum += budget;
            }

            if(sum <= M){ 
                answer = mid; 
                start = mid + 1;
            } else { 
                end = mid - 1;
            }
        }
        return answer;
    }
}

리팩토링 2

  • Intstream으로 max값을 구한다.
  • 람다식과 stream을 사용하여 for-each문을 개선했다. Math.min() 메서드에서는 가변변수는 사용할 수 없으므로 중간값(mid) 변수를 final 상수로 선언했다.
import java.util.stream.IntStream;

class Solution {
    public int solution(int[] budgets, int M) {
        int answer = 0;
        int start = 0;
        int end = IntStream.of(budgets).max().orElse(0); // Intstream으로 max값을 찾을 수 있다.

        while (start <= end) {
            final int mid = (end + start) / 2; //mid는 가변변수 사용할 수 없으므로 final 상수로 바꿔준다.
						int sum = IntStream.of(budgets)
                    .map(budget -> Math.min(budget, mid)) //budget을 mid와 비교하여 작은 값을 선택한다.
                    .sum();

            if(sum <= M){ 
                answer = mid; 
                start = mid + 1;
            } else { 
                end = mid - 1;
            }
        }
        return answer;
    }
}

이진탐색 알고리즘

  • 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
    • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
  • 시간 복잡도는 0(logN)을 보장한다.

이진탐색 소스코드 구현

public class Main {
    public static void main(String[] args) {
        int arr[] = {20, 30, 15, 17};
        int target = 15; 
        int answer = 0;
        int start = 0;
        int end = arr.length -1; 

        while (start <= end) {
            int mid = (start + end) / 2;
            // 찾은 경우 중간점 인덱스 반환
            if (arr[mid] == target) answer  = mid;
                // 중간값의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
            else if (arr[mid] > target) end = mid -1;
                // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
            else start = mid + 1;
        }

        System.out.println(answer + 1);
    }
}

파라메트릭 서치

  • 파라메트릭 서치란 최적화(함수의 값을 최대한 높이거나, 낮춘다.) 문제를 결정 문제로 바꾸어 해결하는 기법입니다.
    • 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
  • 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

You may also enjoy