1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
"""
탐욕법(greedy)
[1, 0, 3, 1, 2]
[0, 3, 0, 4, 0]

뒤에서부터 시작하여 0이상 싣게될때 위치
두 배열이 넘칠때 위치에서 비움
같은 위치에서 반복가능

two pointer
시간복잡도: O(c*n)
공간복잡도: O(c*n)
"""
from collections import deque

def solution(cap, n, deliveries, pickups):
    answer = 0

    deliveries_end = deque()
    pickups_end = deque()
    loads = [0, 0]
    d_index = len(pickups) - 1
    p_index = len(pickups) - 1

    while d_index > -1:
        diff = loads[0] + deliveries[d_index] - cap
        if loads[0] == 0 and deliveries[d_index] > 0:
            deliveries_end.append(d_index)
        if diff <= 0:
            loads[0] += deliveries[d_index]
            deliveries[d_index] = 0
        elif diff > 0:
            deliveries[d_index] -= cap - loads[0]
            loads[0] = 0
            continue
        d_index -= 1
    while p_index > -1:
        diff = loads[1] + pickups[p_index] - cap
        if loads[1] == 0 and pickups[p_index] > 0:
            pickups_end.append(p_index)
        if diff <= 0:
            loads[1] += pickups[p_index]
            pickups[p_index] = 0
        elif diff > 0:
            pickups[p_index] -= cap - loads[1]
            loads[1] = 0
            continue
        p_index -= 1

    if len(deliveries_end) > 0 and len(pickups_end) > 0:
        min_len = len(deliveries_end) if len(deliveries_end) < len(pickups_end) else len(pickups_end)
        for _ in range(min_len):
            d_last = deliveries_end.popleft()
            p_last = pickups_end.popleft()
            answer += 2 * (p_last + 1 if p_last > d_last else d_last + 1)
        while len(deliveries_end) > 0:
            answer += 2 * (deliveries_end.popleft() + 1)
        while len(pickups_end) > 0:
            answer += 2 * (pickups_end.popleft() + 1)

    return answer