파이썬 알고리즘: 예산 안에서 구매할 수 있는 최대 자동차 대수 구하기

판매 중인 자동차들의 가격 목록과 예산 k가 주어졌을 때, 우리가 구매할 수 있는 최대 자동차 대수를 구하는 문제를 생각해 봅시다.

예를 들어 입력이 [80, 20, 10, 30, 80]이고 k = 85라면, 출력은 3이 됩니다. 가격이 10, 20, 30인 세 대의 자동차를 구매하면 총액이 60으로 예산 범위 안에 들기 때문입니다.

문제 해결 접근 방식

이 문제는 그리디(Greedy) 알고리즘으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 '가장 저렴한 차부터 구매하면 최대한 많은 차를 살 수 있다'는 것입니다. 다음 단계로 진행합니다.

• 구매 횟수를 저장할 변수 count를 0으로 초기화합니다.
• 가격 목록 prices를 오름차순으로 정렬합니다.
• 목록의 처음부터 끝까지 순회하며 다음을 반복합니다.
  • 현재 가격 prices[i]가 남은 예산 k 이하라면, 예산에서 해당 가격을 빼고 count를 1 증가시킵니다.
  • 그렇지 않다면, 더 이상 구매할 수 없으므로 반복문을 종료합니다.
• 최종적으로 count를 반환합니다.

정렬된 상태에서 순회하기 때문에 특정 가격이 예산을 초과하는 순간, 이후의 모든 가격도 예산을 초과하게 됩니다. 따라서 즉시 반복문을 빠져나와도 정확한 결과를 얻을 수 있습니다.

구현 예제

class Solution:
    def solve(self, prices, k):
        count = 0
        prices.sort()
        for i in range(len(prices)):
            if(prices[i] <= k):
                k = k - prices[i]
                count += 1
            else:
                break
    return count

ob = Solution()
p = [80, 20, 10, 30, 80]
print(ob.solve(p, 85))

입력

[80, 20, 10, 30, 80], 85

출력

3

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 정렬에 의해 결정되며, O(n log n)입니다. 여기서 n은 자동차의 개수입니다. 정렬 이후의 순회 과정은 선형 시간 O(n) 내에서 완료되므로 전체 성능은 매우 효율적입니다. 공간 복잡도는 추가 배열 없이 제자리(in-place) 정렬을 사용하므로 O(1)입니다.