프로그래머스 2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기 문제 풀이 (Python, Greedy)

프로그래머스 2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기 문제 바로가기

문제 접근

문제가 쉬워보이지는 않았던 것 같은데 규칙만 잘 찾으면 쉽게 풀 수 있는 문제인듯 하다.
우선 첫번째로 가장 먼 곳부터 택배를 배달, 수거를 해야 된다. 그 이유는 어차피 배달은 모두 다녀야 하는 상황이다. 하지만 수거할 때 멀리서부터 수거해온다면 오면서 하나라도 더 수거해 총 이동거리를 줄일 수 있다. (나중에 수거하러 가지 않아도 된다는 말)
두번째로는 배달과 수거를 따로 생각한다면 편리한 것 같다.
예제 1번에서 택배를 3개만 들고 가는 것 때문에 처음에는 초기에 택배의 개수조차 고려해야 해야하는지에 대해서 고민을 했는데 배달과 수거를 따로 생각한다면 이 문제를 해결할 수 있다.
수거할때는 무조건 트럭이 비어있다고 생각하고 수거하면 된다.

문제 풀이

수거 또는 배달할게 없는 집은 삭제

pop으로 수거또는 배달할게 없다면 삭제해준다.

def delete_zero():
        while 1:
            if deliveries and deliveries[-1] == 0:
                deliveries.pop()
            else:
                break
        while 1:
            if pickups and pickups[-1] == 0:
                pickups.pop()
            else:
                break

배달 구현

배달을 하고도 택배 상자가 남았다면 다음 집으로 배달하는 형식이다.
들고온 택배상자가 다 떨어지면 함수를 종료한다.

  # 배달
        if deliveries:
            for i in range(len(deliveries)-1, -1, -1):
                if d <= deliveries[i]:
                    deliveries[i] -= d
                    break
                else:
                    d -= deliveries[i]
                    deliveries[i] = 0

수거 구현

트럭에 공간이 남았다면 수거해야 하는 택배 상자를 집어 넣고 다음 집으로 이동하여 반복한다.
만약 트럭에 택배상자가 꽉 차면 반복문을 종료한다.

# 수거
        if pickups:
            for i in range(len(pickups)-1, -1, -1):
                if pickups[i] >= p:
                    pickups[i] -= p
                    break
                else:
                    p -= pickups[i]
                    pickups[i] = 0

통합

while 1:
        delete_zero() # 집이 배달 또는 수거할 것이 없다면 삭제
        next_n = max(len(deliveries), len(pickups)) # 배달 또는 수거할 집 중 더 멀리 있는 곳으로 가야함
        answer += (next_n * 2) # 현재까지 총 이동거리 + 간 거리 * 2
        if next_n == 0: # 종료조건
            break
        
        d = cap
        p = cap
        # 배달과 수거 구현
        # 배달
        if deliveries:
            for i in range(len(deliveries)-1, -1, -1):
                if d <= deliveries[i]:
                    deliveries[i] -= d
                    break
                else:
                    d -= deliveries[i]
                    deliveries[i] = 0
        # 수거
        if pickups:
            for i in range(len(pickups)-1, -1, -1):
                if pickups[i] >= p:
                    pickups[i] -= p
                    break
                else:
                    p -= pickups[i]
                    pickups[i] = 0

제출 코드

def solution(cap, n, deliveries, pickups):
    # 끝에서부터 집의 배달의 개수, 수거 개수를 합함
    # 만약 cap보다 수거 개수
    answer = 0
    next_n = n
    
    def delete_zero():
        while 1:
            if deliveries and deliveries[-1] == 0:
                deliveries.pop()
            else:
                break
        while 1:
            if pickups and pickups[-1] == 0:
                pickups.pop()
            else:
                break
    while 1:
        delete_zero() # 집이 배달 또는 수거할 것이 없다면 삭제
        next_n = max(len(deliveries), len(pickups)) # 배달 또는 수거할 집 중 더 멀리 있는 곳으로 가야함
        answer += (next_n * 2) # 현재까지 총 이동거리 + 간 거리 * 2
        if next_n == 0: # 종료조건
            break
        
        d = cap
        p = cap
        # 배달과 수거 구현
        # 배달
        if deliveries:
            for i in range(len(deliveries)-1, -1, -1):
                if d <= deliveries[i]:
                    deliveries[i] -= d
                    break
                else:
                    d -= deliveries[i]
                    deliveries[i] = 0
        # 수거
        if pickups:
            for i in range(len(pickups)-1, -1, -1):
                if pickups[i] >= p:
                    pickups[i] -= p
                    break
                else:
                    p -= pickups[i]
                    pickups[i] = 0
    
    return answer