택배 배달과 수거하기

택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

문제

풀이

이 문제에 키포인트는 그리디이다. 무조건 멀리 있는 것을 우선으로 배달해야 하고, 상자를 수거해야 한다.

1. deliveries, pickups가 비워질 때 까지 while문을 실행시킨다.
   

2. deliveries의 가장 먼곳, pickups의 가장 먼곳이 0일 때를 없애준다. -> 이부분 중요!!! 케이스 2번 해결
   

3. deliveries의 길이, pickups의 길이 중 최대값을 구하고 *2를한다. 왕복이므로
   

4. cap의 개수 만큼 배달하고, 수거한다. 이 과정 중 전부 배달,수거되는 인덱스는 pop해준다.
   

def solution(cap, n, deliveries, pickups):
    answer = 0
    while True:
        if not deliveries and not pickups:
            break
        for i in range(len(deliveries) - 1, -1, -1):
            if deliveries[i] == 0:
                deliveries.pop(i)
            else:
                break
        for i in range(len(pickups) - 1, -1, -1):
            if pickups[i] == 0:
                pickups.pop(i)
            else:
                break
                
                
        answer += 2* (max(len(deliveries), len(pickups)))
        cnt = cap
        
        for i in range(len(deliveries) - 1, -1, -1):
            if deliveries[i] <= cnt:
                cnt -= deliveries[i]
                deliveries.pop(i)
            else:
                deliveries[i] -= cnt
                break
        cnt = cap
        for i in range(len(pickups) - 1, -1, -1):
            if pickups[i] <= cnt:
                cnt -= pickups[i]
                pickups.pop(i)
            else:
                pickups[i] -= cnt
                break
    return answer
                

결과