🐹 택배 배달과 수거하기

1. 문제 링크

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

2. 코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    # 배열이 모두 0인 경우
    zero_list = [0] * n
    if deliveries == pickups == zero_list:
        return answer
    
    while deliveries or pickups:
        answer += max(len(deliveries), len(pickups))
        d_limit, p_limit = cap, cap
        while deliveries:
            # 배달 가능, 배달 불필요 집
            if deliveries[-1] <= d_limit:
                d_limit -= deliveries.pop()
            # 부분 배달
            else:
                deliveries[-1] -= d_limit
                break
        while pickups:
            # 픽업 가능, 픽업 불필요 집
            if pickups[-1] <= p_limit:
                p_limit -= pickups.pop()
            # 부분 픽업
            else:
                pickups[-1] -= p_limit
                break
            
    return answer * 2

• 정확성

  테스트 1 〉	통과 (0.01ms, 10.3MB)
  테스트 2 〉	통과 (0.00ms, 10.1MB)
  테스트 3 〉	통과 (0.02ms, 10.2MB)
  테스트 4 〉	통과 (0.01ms, 10.1MB)
  테스트 5 〉	통과 (0.03ms, 10.3MB)
  테스트 6 〉	통과 (0.02ms, 10.2MB)
  테스트 7 〉	통과 (0.46ms, 10.2MB)
  테스트 8 〉	통과 (1.24ms, 10.4MB)
  테스트 9 〉	통과 (5.51ms, 10.3MB)
  테스트 10 〉	통과 (4.17ms, 10.3MB)
  테스트 11 〉	통과 (3.61ms, 10.3MB)
  테스트 12 〉	통과 (2.89ms, 10.3MB)
  테스트 13 〉	통과 (1.15ms, 10.3MB)
  테스트 14 〉	통과 (1.31ms, 10.1MB)
  테스트 15 〉	통과 (21.60ms, 12.1MB)
  테스트 16 〉	통과 (1288.20ms, 12.1MB)
  테스트 17 〉	통과 (102.19ms, 12.2MB)
  테스트 18 〉	통과 (45.73ms, 12.1MB)
  테스트 19 〉	통과 (38.29ms, 12.2MB)
  테스트 20 〉	통과 (39.27ms, 12 MB)

3. 해설

그리디 알고리즘을 사용하여 문제를 해결한다.

가장 멀리 있는 집부터 트럭 용량만큼 배달과 픽업을 진행한다. 배달 혹은 픽업이 다 완료된 집은 스택에서 제거해버린다.

스택의 길이가 방문해야하는 가장 먼 길이이므로 배달과 픽업 중 더 큰 값을 더해준다. (둘은 동시에 이루어지므로)

마지막으로 왕복을 계산해야하므로 answer에 2를 곱해준다.