Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 매일 먹을 수 있는 사과의 최대 개수 구하기

문제 설명

길이가 n으로 같은 두 배열 days와 apples가 주어진다고 가정해 봅시다. 어떤 특별한 사과나무는 n일 동안 연속적으로 매일 사과를 열매맺습니다. i번째 날에는 apples[i]개의 사과가 열리고, 이 사과들은 days[i]일 후에 썩습니다. 다시 말해, i + days[i]째 날이 되면 해당 사과는 썩어서 더 이상 먹을 수 없게 됩니다.

apples[i] = 0이고 days[i] = 0인 경우, 그날에는 나무에서 사과가 열리지 않는다는 의미입니다. 우리는 하루에 최대 한 개의 사과만 먹을 수 있으며, n일이 지난 후에도 남아 있는 사과가 있다면 계속 먹을 수 있습니다. 이때, 먹을 수 있는 사과의 최대 개수를 구하는 것이 목표입니다.

예시

입력이 다음과 같다고 해보겠습니다.

apples = [1,2,3,5,2]
days = [3,2,1,4,2]

이 경우 출력은 7이 됩니다. 그 이유는 다음과 같습니다.

  • 1일차: 첫날 열린 사과를 먹습니다.
  • 2일차: 둘째 날 열린 사과를 먹습니다.
  • 3일차: 둘째 날 열린 사과를 또 먹습니다. 이날이 지나면 셋째 날 열린 사과는 썩어버립니다.
  • 4일차 ~ 7일차: 넷째 날 열린 사과들을 하루에 하나씩 먹습니다.

풀이 접근 방법: 최소 힙(Min-Heap) 활용

이 문제의 핵심은 그리디(Greedy) 전략입니다. 매일 먹을 수 있는 사과 중에서 가장 빨리 썩는 사과부터 우선적으로 먹는 것이 전체적으로 최대 개수를 보장합니다. 이를 위해 만료일을 기준으로 정렬된 상태를 유지하는 최소 힙(min-heap)을 사용합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. minheap을 새로 생성합니다. day := 0, res := 0으로 초기화합니다.
  2. i를 0부터 len(apples)-1까지 반복합니다.
    • day := i로 설정합니다.
    • 힙이 비어 있지 않고 힙의 최상위 요소의 만료일이 day보다 작으면(이미 썩었으면) 힙에서 제거합니다.
    • nbrApple := apples[i], expiration := i + days[i] - 1로 설정합니다.
    • nbrApple > 0이면 (expiration, nbrApple) 쌍을 힙에 삽입합니다.
    • 힙이 비어 있지 않으면 최상위 요소를 꺼내고 res를 1 증가시킵니다. 꺼낸 사과 개수가 1보다 크면 (date, apple-1)을 다시 힙에 넣습니다.
  3. n일이 지난 후에도 힙에 사과가 남아 있는 동안 반복합니다.
    • day를 1씩 증가시키고, 만료일이 지나간 사과를 힙에서 제거합니다.
    • 힙이 비면 반복을 종료합니다.
    • 그렇지 않으면 최상위 요소를 꺼내 res를 1 증가시키고, 남은 개수가 1보다 크면 (date, apple-1)을 다시 삽입합니다.
  4. 최종적으로 res를 반환합니다.

파이썬 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

import heapq

def solve(apples, days):
    minheap = []
    heapq.heapify(minheap)
    day = 0
    res = 0

    for i in range(len(apples)):
        day = i

        while minheap and minheap[0][0] < day:
            heapq.heappop(minheap)

        nbrApple = apples[i]
        expiration = i + days[i]-1

        if nbrApple > 0:
            heapq.heappush(minheap, (expiration, nbrApple))

        if minheap:
            date, apple = heapq.heappop(minheap)
            res += 1
            if apple > 1:
                heapq.heappush(minheap, (date, apple-1))

    while minheap:
        day += 1
        while minheap and minheap[0][0] < day:
            heapq.heappop(minheap)
        if minheap == []:
            break
        date, apple = heapq.heappop(minheap)
        res += 1
        if apple > 1:
            heapq.heappush(minheap, (date, apple-1))

    return res

apples = [1,2,3,5,2]
days = [3,2,1,4,2]
print(solve(apples, days))

입력

[1,2,3,5,2],[3,2,1,4,2]

출력

7

복잡도 분석

각 사과 배치는 힙에 최대 한 번 삽입되고 제거되므로, 시간 복잡도는 O(N log N)입니다. 여기서 N은 배열의 길이이며, 공간 복잡도는 힙에 저장되는 요소 수에 비례하여 O(N)입니다. 이 방식은 n일 이후에도 남은 사과를 효율적으로 처리하면서 항상 썩기 전에 먹을 수 있는 사과를 우선 소비하기 때문에 최적의 결과를 보장합니다.