[프로그래머스] 택배 배달과 수거하기 - 파이썬

문제

🔗 : 프로그래머스 - 택배 배달과 수거하기

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

 

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

 

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

 

배달 및 수거 과정

 

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수  cap , 배달할 집의 개수를 나타내는 정수  n  , 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열  deliveries  와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열  pickups 가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

 

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i] 는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i] 는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries[i] ≤ 50
  • 0 ≤ pickups[i] ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

 

입출력 예

 

---

레벨2 안같은 레벨2 문제이며,

아직도 못친해진 그리디 문제.

 

풀이 참고: https://school.programmers.co.kr/questions/43364

 

그리디 문제는 사실 손도 못대겠어서 위의 풀이를 많이 참조했다.ㅠㅠ

 

위 링크에서 얘기하는 포인트는 다음과 같다.

- i 거리의 집에 배달하거나 수거할 상자가 남았다면, 어차피 i만큼 이동해야된다.

- 물류창고에서 출발해서 다시 돌아오는 길에는 무조건 cap만큼 배달 / 수거가 가능하다.

- i까지 갔는데 미처 처리 못한 배달/수거 상자가 있을 경우, i까지 다시 와야 된다.

 

→ 즉, cap만큼 배달/수거 가능한 최장거리 i에서부터 뒤로 탐색해나간다.

 

 

배열을 뒤에서부터 탐색해가면서, cap만큼 배달과 수거를 진행한다.

이 때, i만큼 가는 길에 배달 먼저/수거 먼저 여부는 트럭이 판단한다.

 

예를 들어 5번 집까지 가는 길에 4번 → 5번집을 가면서 배달을 먼저 하고

5번에서 돌아오는 길에 5번 → 4번 → 3번 가면서 수거를 하던지,

 

4번 집에 배달 하나, 상자 2개를 수거하고

5번 집에 배달 두개하고 돌아오는 길에 4번 집의 택배 2개를 마저 수거..뭐 등등등 하면서 알아서 오던지

 

어차피 5번 집을 찍고 돌아오는 길에 모든 일이 이루어지기 때문에, 배달과 수거의 순서는 중요하지 않다.

다시 말하면 배달 / 수거는 별개의 task로 생각한다.

 

 

여기까지 아이디어는 이해했고, 코드화하는 과정에서

 

[ 루프를 돌면서 배달하거나 수거할 택배가 있는 집을 찾는 데 까지 탐색한다. ]

이 부분을 파이썬으로 풀면 백퍼 시간초과가 날 것 같았다....

 

그렇기 때문에

(n-1)부터 각 집을 거꾸로 돌면서,

 

- 배달 적재를 관리하는 변수와 수거 적재를 관리하는 변수에 i번째 집의 배달 / 수거 개수를 각각 더해준다.

- 만약 지금 트럭에 적재된 개수가 0보다 커졌다면,

    - 지금 적재된 양은 몇 번을 왕복해야 마칠 수 있는지 count 한다.

    - 각각의 적재 관리 변수에 (횟수 x 적재 용량) 만큼 빼서 이동 후 현재 적재된 개수를 저장한다.

- 현재 집의 위치와 왕복 횟수를 곱해서 이동 거리를 계산한다.

 

아이디어를 참고해서 나름 나만의 방식대로 풀어봤다...

여전히 어렵다ㅜㅜ

 

코드

def solution(cap, n, deliveries, pickups):
    answer = 0

    left_p, left_d = 0, 0
    for i in range(n - 1, -1, -1):
        cnt = 0

        left_p += deliveries[i]
        left_d += pickups[i]

        if left_p > 0 or left_d > 0:
            cnt = (max(left_d, left_p) + cap - 1) // cap
            left_d -= cap * cnt
            left_p -= cap * cnt
    
        answer += (i + 1) * 2 * cnt

    return answer