[Python] 프로그래머스 카카오 문제 - 택배 배달과 수거하기 - 그리디

Lv2. 문제링크

1. 2023 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

📎알고리즘

n이 10만 개라는 것에서 n^2 이 걸리는 완전 탐색은 배제해야 함을 알 수 있다. 그리디 하게 풀어야 하는 문제이다.

 

일단, 처음부터 제일 멀리 있는 집에 가서 작업을 최대한 끝내야 먼 곳을 최소한으로 갈 수 있을 것이다.

그래서 가장 먼 집부터 탐색해서 배달, 수거할 상자 개수를 각각의 변수에 더해주고

이 값을 각각 cap(트럭 용량)만큼 빼준다.

 

이때, cap 만큼 빼준 값이 양수라면, 수거하거나 배달할 상자가 남은 것이므로 한번 더 와야 한다. 따라서 cap을 뺀 값이 둘 다 음수가 될 때까지 while문을 더 도는 것이다.

 

만약 둘 다 음수가 되었다면 이제 그 집은 더 이상 방문할 필요가 없는 것이고, 다음 집으로 이동한다. 이 때 다음 집 수거, 배달할 상자의 개수들을 각각 또 변수에 더하는데, 이 값의 결과도 음수라면, 이전 경로에서 트럭 용량이 남아 오는 길에 다음 집 것까지 처리를 하고 온 경우를 뜻하므로 answer에 경로를 추가하지 않고 다음 for문으로 넘어간다.

 

경로를 계산하는 식은 항상 왔다 갔다 해야 하니까 (편도 거리 * 2) 하는 식으로 계산을 해줬다.

 

 

⌨코드

def solution(cap, n, deliveries, pickups):
    deliveries=deliveries[::-1] #역순으로 뒤집기
    pickups=pickups[::-1]
    
    cnt_deliver=0
    cnt_pickup=0
    
    answer=0
    for i in range(n):
        cnt_deliver += deliveries[i]
        cnt_pickup += pickups[i]
        
        while cnt_deliver > 0 or cnt_pickup > 0: #둘다 음수일 때 다음으로 이동
            cnt_deliver -= cap
            cnt_pickup -= cap
            
            answer+= (n-i)*2 #갔다가 돌아와야 하므로
    
    return answer

 

💻제출결과