[2023 KAKAO BLIND RECRUITMENT] 택배 배달과 수거하기

문제

• 일렬로 나열된 N개의 집에 택배를 배달하면서 빈 박스를 수거해야 한다. 
• 트럭에는 상자를 최대 cap개 실을 수 있다. 
• 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리 구하기
• n 번째 집과 물류창고와의 거리는 n 이다.

 

• 1 <= cap <= 50
• 1 <= N <= 100,000

 

풀이

• 우선 배달해야할 것과 수거할 박스가 없다면, 0을 리턴한다. (예외 처리)
• 물류창고에서 트럭에 박스를 가득 채운 다음 마지막 집에서부터 차례로 배달을 하면서 박스를 수거하고, 물류창고로 돌아온다. 이를 모든 집에 배달할 상자와 수거할 상자가 없을 때까지 반복한다.

 

"""
- 트럭에 재활용 상자 cap 만큼 실을 수 있고
- 트럭은 각 집에 배달하면서 빈 재활용 택배 상자들 수거 후 물류 창고에 내림
- 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리 구하기

- 마지막 집을 먼저 가기 (어차피 가야함!)
"""
def starting_point(array) :
    for i in range(len(array)-1, -1, -1) :
        if array[i] != 0 :  # 배달 또는 수거할 상자가 남아있다면 해당 위치 반환
            return i
        else :              # 배달을 완료했다면 제거
            array.pop()

def moves(array, cap) :
    start = cnt = 0                   # 시작지점, 상자 개수
    if array :
        start = starting_point(array) # 배달 or 수거 시작지점 찾기
        while True :
            if not array: break       # 배달 or 수거할게 없다면 stop
            # 최대 cap까지 배달하기
            if cnt + array[-1] <= cap :
                cnt += array[-1]
                array.pop()
            else:
                array[-1] -= (cap - cnt)
                cnt = cap
                break
    return start
    
def solution(cap, n, deliveries, pickups):
    answer = 0
    # 예외처리 -> 배달 또는 수거할 것이 없음
    if sum(deliveries) + sum(pickups) == 0 :
        return 0
    
    # 모든 상자를 배달하고 수거하기
    while deliveries or pickups :        
        start_d = moves(deliveries, cap) # 배달하기
        start_p = moves(pickups, cap)    # 수거하기

        # 거리 더하기
        answer += max(start_d, start_p) + 1
        
    return answer * 2