[파이썬, Java] 택배 배달과 수거하기

⭐ 나의 풀이

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int delivery = 0;
        int pickup = 0;
        
        for(int i = n-1; i >= 0; i--){
            delivery += deliveries[i];
            pickup += pickups[i];
            
            while(delivery > 0 || pickup > 0){
                delivery -= cap;
                pickup -= cap;
                answer += (i+1) * 2;
            }
        }
        
        return answer;
    }
}

이 문제의 핵심은 가장 먼 거리부터 배달, 수거를 완료하는 것이다.

 

 

# 실패
def solution(cap, n, deliveries, pickups):
    answer = 0
    cur = n - 1

    while True:
        flag = False
        tmp = 0
        weight = 0
        for i in range(cur, -1, -1):
            if deliveries[i] != 0 and deliveries[i] + weight <= cap:  # 택배 싣기
                weight += deliveries[i] + weight
                deliveries[i] = 0
                flag = True
            if flag:
                tmp = max(tmp, i)
        for j in range(tmp, -1, -1) :
            if pickups[j] != 0 and weight - pickups[j] >= 0:  # 택배 수거
                weight -= pickups[j]
                pickups[j] = 0
                flag = True
            if flag:
                tmp = max(tmp, j)
        answer += (tmp + 1) * 2
        if sum(deliveries) == 0 and sum(pickups) == 0:
            break
        if deliveries[cur] == 0 and deliveries[cur] == 0:
            cur -= 1

    return answer

테케는 통과하는데 제출하면 시간 초과가 나고 😢

거리가 먼 곳부터 처리한다.

 

 

🐘 다른 사람 풀이

# https://oh2279.tistory.com/147
def solution(cap, n, deliveries, pickups):
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]
    answer = 0

    have_to_deli = 0
    have_to_pick = 0

    for i in range(n) :
        have_to_deli += deliveries[i]
        have_to_pick += pickups[i]

        while have_to_deli > 0 or have_to_pick > 0 :
            have_to_deli -= cap
            have_to_pick -= cap
            answer += (n - i) * 2

    return answer

거리가 먼 곳부터 처리할려고 배열을 뒤집었다.

배달할 곳 have_to_deli 또는 수거할 곳 have_to_pick이 양수면 트럭이 왕복 이동 answer += (n-i)*2

 

 

 

문제 출처 👇

https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=java 

프로그래머스