[Java/Algorithm] Greedy - 제한된 합 이내에서 원소를 최대로 선택하기

문제 설명

길이가 N인 정수 배열 A가 주어진다. 이 배열에서 합이 K를 넘지 않도록 최대한 많은 원소를 선택하려고 한다. 선택할 수 있는 최대 원소 개수를 반환한다.

예시
입력: A = [1, 3, 2, 5, 4], K = 7
출력: 3
설명: 1, 2, 3을 선택하면 합이 6이 되어 최대 3개의 원소를 선택할 수 있다.

풀이 과정

제한된 범위 안에서 최대한 많은 원소를 선택하는 방식에서 그리디 알고리즘이 먼저 떠올랐습니다. 우선, 배열을 오름차순으로 정렬합니다. 최대한 많은 원소를 선택하는 것이 목적이기 때문에, 숫자가 가장 작은 원소부터 합산에 넣어줘야 합니다.

Arrays.sort(A);

정렬을 마쳤으면 작은 값을 가진 원소부터 더해서 K를 넘지 않는 선에서 합을 구하고, 원소를 더할 때마다 횟수도 별도로 계산합니다.

int cnt = 0;
int sum = 0;

for (int i = 0; i< A.length; i++) {
	if (sum + A[i] < K) { // K를 넘지 않으면
    	sum += A[i]; // 합산 진행
        cnt++; // 카운트 증가
    } else { // K를 넘으면
    break; // 반복문 중지
    }
]

반복문 계산이 끝나면 계산된 횟수가 최대 횟수가 됩니다.

최종 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] A, int K) {
        // 배열을 오름차순으로 정렬
        Arrays.sort(A);
        
        int count = 0;
        int sum = 0;

        // 작은 값부터 더해가면서 K를 넘지 않도록
        for (int i = 0; i < A.length; i++) {
            if (sum + A[i] <= K) {
                sum += A[i];
                count++;
            } else {
                break; // 더 이상 원소를 추가할 수 없으므로 종료
            }
        }

        return count; // 최종적으로 선택한 원소의 개수 반환
    }
}