🦊 택배 배달과 수거하기

1. 문제 링크

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

2. 코드

• 실행 결과

    채점을 시작합니다.
    정확성  테스트
    테스트 1 〉	통과 (0.02ms, 10.1MB)
    테스트 2 〉	통과 (0.01ms, 10.3MB)
    테스트 3 〉	통과 (0.04ms, 10.4MB)
    테스트 4 〉	통과 (0.02ms, 10.4MB)
    테스트 5 〉	통과 (0.05ms, 10.1MB)
    테스트 6 〉	통과 (0.03ms, 10.1MB)
    테스트 7 〉	통과 (0.77ms, 10.4MB)
    테스트 8 〉	통과 (3.28ms, 10.5MB)
    테스트 9 〉	통과 (7.97ms, 10.3MB)
    테스트 10 〉	통과 (6.25ms, 10.3MB)
    테스트 11 〉	통과 (3.26ms, 10.4MB)
    테스트 12 〉	통과 (2.60ms, 10.4MB)
    테스트 13 〉	통과 (2.26ms, 10.4MB)
    테스트 14 〉	통과 (2.25ms, 10.3MB)
    테스트 15 〉	통과 (34.50ms, 15.8MB)
    테스트 16 〉	통과 (1845.92ms, 18.8MB)
    테스트 17 〉	통과 (162.40ms, 18.1MB)
    테스트 18 〉	통과 (95.86ms, 19.5MB)
    테스트 19 〉	통과 (62.95ms, 17.3MB)
    테스트 20 〉	통과 (77.38ms, 18.9MB)
    채점 결과
    정확성: 100.0
    합계: 100.0 / 100.0
  

# 오른쪽부터 남은 개수 감소
def minus_cap(cap, n, indexes, arr):
    left_cap = cap
    
    while indexes and left_cap > 0:
        idx = indexes[-1]
        # 아직 남은 상태
        if arr[idx] > left_cap:
            arr[idx] -= left_cap
            left_cap = 0
        else:
            left_cap -= arr[idx]
            arr[idx] = 0
            indexes.pop()

# 배달할 개수를 오른쪽부터 감소시킴
def solution(cap, n, deliveries, pickups):
    answer = 0
    # 배달할 인덱스 역순
    delivery_idx = []
    for i in range(n):
        if deliveries[i] > 0:
            delivery_idx.append(i)
    # 픽업 인덱스 역순
    pickup_idx = []
    for i in range(n):
        if pickups[i] > 0:
            pickup_idx.append(i)

    while True:
        current_delivery_idx = -1
        current_pickup_idx = -1
        if delivery_idx:
            current_delivery_idx = delivery_idx[-1]
            minus_cap(cap, n, delivery_idx, deliveries)
        if pickup_idx:
            current_pickup_idx = pickup_idx[-1]
            minus_cap(cap, n, pickup_idx, pickups)
        # 더이상 남은게 없으면 종료
        if current_delivery_idx == -1 and current_pickup_idx == -1:
            break
        
        # 한쪽만 남은 경우 보정
        if current_delivery_idx == -1:
            current_delivery_idx = current_pickup_idx
        if current_pickup_idx == -1:
            current_pickup_idx = current_delivery_idx
        
        answer += current_delivery_idx + 1 + current_pickup_idx + 1 + abs(current_delivery_idx - current_pickup_idx)

    return answer

• 해설

  항상 배달 → 픽업 순으로 이루어짐

  예시에서도 볼 수 있듯이 가장 먼 거리에 있는 집 부터 배달과 픽업이 이루어진다고 할 수 있음

  원소가 존재하는 idx 만 저장

  각 배열의 제일 오른쪽 인덱스를 가져옴

  그 인덱스부터 역순으로 남은 cap 만큼 원소 값을 감소시킴

  answer 에 배달idx, 픽업idx, (배달idx - 픽업idx) 를 더함