[python] 프로그래머스 - 택배 배달과 수거하기

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

# n개의 집에서 i번째 집은 i만큼 떨어져있고 모든 집은 일자로 놓여있음.
# 트럭에는 cap개 싣을 수 있다.
# 모든 집에 배달/수거해야하는 택배 개수를 알고 있다.

# 모든 택배를 보내고 수거하는데 드는 최소 이동 거리

 

---

풀이

 

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    while True:
        while deliveries and deliveries[-1] == 0:
            deliveries.pop()

        while pickups and pickups[-1] == 0:
            pickups.pop()

        answer += max(len(deliveries), len(pickups)) * 2

        if not deliveries and not pickups:
            break

        d_cap = cap
        i = len(deliveries) - 1

        while deliveries and d_cap > 0:
            if deliveries[i] >= d_cap:
                deliveries[i] -= d_cap
                d_cap = 0
            else:
                d_cap -= deliveries[i]
                deliveries[i] = 0

            i -= 1

            if i < 0:
                break

        p_cap = cap
        i = len(pickups) - 1

        while pickups and p_cap > 0:
            if pickups[i] >= p_cap:
                pickups[i] -= p_cap
                p_cap = 0
            else:
                p_cap -= pickups[i]
                pickups[i] = 0

            i -= 1

            if i < 0:
                break

    return answer

def solution(cap, n, deliveries, pickups):
    answer = 0
 	
    # 초기화
    d_dis = []
    d_dict = dict()
    
    p_dis = []
    p_dict = dict()
        
    for distance in range(n):
        if deliveries[distance] != 0:
            d_dis.append(distance + 1)
            d_dict[distance + 1] = deliveries[distance]
        
        if pickups[distance] != 0:
            p_dis.append(distance + 1)
            p_dict[distance + 1] = pickups[distance]
    
    # 이동 거리 계산
    while len(d_dis) > 0 or len(p_dis) > 0:
        far_d_distance = 0
        can_deliver = cap

        while can_deliver > 0 and len(d_dis) > 0: # d_dis의 길이가 0보다 클때만 진행
            farest_distance = d_dis[-1] # 가장 멀리 있는 거리를 불러옴.

            if far_d_distance == 0: # 가장 멀리 이동해야하는 거리 저장
                far_d_distance = farest_distance

            if can_deliver >= d_dict[farest_distance]:
                can_deliver -= d_dict[farest_distance]
                d_dict[farest_distance] = 0

                d_dis.pop()
            else:
                d_dict[farest_distance] -= can_deliver
                can_deliver = 0

        far_p_distance = 0
        can_pickip = cap

        while can_pickip > 0 and len(p_dis) > 0:
            farest_distance = p_dis[-1]

            if far_p_distance == 0:
                far_p_distance = farest_distance

            if can_pickip >= p_dict[farest_distance]:
                can_pickip -= p_dict[farest_distance]
                p_dict[farest_distance] = 0

                p_dis.pop()
            else:
                p_dict[farest_distance] -= can_pickip
                can_pickip = 0

        answer += max(far_d_distance, far_p_distance) * 2

    return answer

 

---

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들