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

2023 KAKAO BLIND RECRUITMENT - 150369. 택배 배달과 수거하기

[Lv. 2]

 

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

프로그래머스

 

풀이

문제를 읽고 나서의 초견은, Greedy하게 접근하면 되지 않을까? 였다.

제일 먼 곳에서부터 배달/수거를 cap만큼 꽉꽉 채워서 왔다갔다 하는 식으로..

일단 구현해보자.

 

조금 유의하며 코드를 작성했던 부분은, deliveries나 pickups 배열에서 값이 존재하는(0이 아닌) 가장 큰 index를 찾을 때는, 그때마다 탐색하며 찾으면 O(n)이므로, 따로 index pointer를 선언하여 처리해 주었다.

index pointer로 처리하지 않고, while문의 조건식 등도 sum이나 max함수같은 O(n)인 함수를 사용하게 되면, 자연히 시간초과가 난다.

 

AC.

def solution(cap, n, deliveries, pickups):
    deliverPointer = n-1
    pickupPointer = n-1
    answer = 0

    while pickups[pickupPointer] != 0 or deliveries[deliverPointer] != 0:
        length = []
        # 제일 먼 집부터 배달을 처리해나감
        temp = 0
        for i in range(deliverPointer, -1, -1):
            if cap >= temp + deliveries[i]:
                temp += deliveries[i]
                deliveries[i] = 0
                deliverPointer -= 1
                length.append(i)
            else:
                # cap < temp + deliveries[i]
                deliveries[i] -= cap-temp
                temp = cap
                length.append(i)
                break

        # 그리고 갔다 오면서 수거도
        temp = 0
        for i in range(pickupPointer, -1, -1):
            if cap >= temp + pickups[i]:
                temp += pickups[i]
                pickups[i] = 0
                pickupPointer -= 1
                length.append(i)
            else:
                # cap < temp + pickups[i]
                pickups[i] -= cap-temp
                temp = cap
                length.append(i)
                break

        if length:
            answer += (max(length)+1)*2
            
    return answer