[2023KAKAO BLIND RECRUITMENT-택배 배달과 수거하기]

문제 - 링크

문제 해결 아이디어

• 실제로 왔다갔다를 구현하지 않고 다음에 택배를 배달해야 하는 위치, 상자를 수거해야 하는 위치를 업데이트 하기 
  -> 문제를 가장 단순한 형태로 바꾸자 
• 가장 먼 지점부터 택배를 배달하고, 상자를 수거한다 

문제 풀이 

1. 택배를 배달해야하는 가장 먼 위치의 집(idx1), 수거 해야하는 가장 먼 위치의 집 인덱스(idx2)부터 시작
2. 매 턴마다 answer += max(idx1, idx2), 두 인덱스 중 더 먼지점까지 이동 
3. cap 만큼 뒷집부터 배달해야 하는 택배 제거, cap 만큼 뒷집부터 수거해야 하는 상자 제거 -> idx1, idx2 갱신 
   -> 이때, idx1, idx2는 다음번 방문 필요한 지점을 의미하므로 값이 0보다 큰 위치를 가르키고 있어야 함 
   -> cap만큼 이동 후에도 가르키는 칸의 값이 0이면 한칸 땡기기 
4. idx1, idx2가 0보다 크거나 같을 때까지 반복 (아직 배달 or 수거할 택배가 남아있음을 의미)

코드 구현

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    idx1, idx2 = -1, -1
    # 배달, 수거 해야하는 가장 먼 지점을 시작인덱스로 세팅 
    for i in range(n-1, -1, -1):
        if deliveries[i] >0:
            idx1 = i 
            break 
    for i in range(n-1, -1, -1):
        if pickups[i] >0:
            idx2 = i 
            break 
    
    # idx1, idx2가 0보다 크거나 같을때까지 반복(아직 배달or수거할 택배가 남아있음)
    while idx1>=0 or idx2>=0:
        answer += max(idx1, idx2)+1 #이동해야 하는 두 거리 중 큰 값을 더해주기
        rem_cap1, rem_cap2 = cap, cap 
        while rem_cap1>0 and idx1>=0: #cap만큼 이동
            if deliveries[idx1]>rem_cap1: #idx1의 택배 갯수가 남아있는 cap보다 크면 해당 인덱스의 택배 모두 처리하지 못함, cap모두 소모 
                deliveries[idx1] -= rem_cap1
                rem_cap1 = 0 
            elif deliveries[idx1] == rem_cap1: #idx1의 택배 갯수가 남아있는 cap과 같으면 해당 인덱스의 택배 모두 처리하고 idx 한칸 땡김, cap 모두 소모 
                deliveries[idx1] = 0 
                idx1-= 1
                rem_cap1 = 0 
            else: #idx1의 택배 갯수가 남은 cap보다 작으면 해당 위치의 택배 모두 처리&인덱스 한칸 앞으로, cap 남음
                rem_cap1 -= deliveries[idx1]
                idx1 -= 1
                continue 
        while rem_cap2>0 and idx2>=0: # 수거하는 택배에 대해서도 마찬가지로 작업 수행함 
            if pickups[idx2]>rem_cap2: 
                pickups[idx2] -= rem_cap2
                rem_cap2 = 0 
            elif pickups[idx2] == rem_cap2:
                pickups[idx2] = 0 
                idx2-= 1
                rem_cap2 = 0 
            else: 
                rem_cap2 -= pickups[idx2]
                idx2 -= 1
                continue 
        # 0인 인덱스 땡기기-> idx1, idx2를 다음에 시작해야하는 위치로 갱신(택배가 남아있는 위치를 가리키도록) 
        while idx1>=0 and deliveries[idx1]==0:
            idx1 -= 1
        while idx2>=0 and pickups[idx2]==0:
            idx2 -= 1

    return answer*2 #왕복거리이므로 정답은 *2배