23.02.16 파이썬 코딩 퀴즈#159 택배 배달과 수거하기 (프로그래머스 스쿨)

이번 문제는 택배 배달과 수거하기 문제이다.

일렬로 나열된 n 개의 집에 택배를 배달하게 되는데, 배달을 다니면서 빈 재활용 택배 상자들도 수거해야 한다.

트럭에 적재 가능한 최대 화물의 수는 cap 개 이고, 트럭은 배달할 상자들을 실어 물류 창고에서 출발해 각 집에 배달을 시작한다. 이 때, 배달 트럭에 적재된 상자 수와 수거할 빈 택배 상자개수를 알 고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구해야 한다.

바로 입출력 예를 통해서 설명을 이해해 보자.

예제 1번을 보면 cap 은 4 이다. 즉 트럭에는 4개의 상자만 적재할 수 있다.

n 은 5이다. 총 5개의 집이 있으며, 집 사이의 거리는 1이다.

deliveries 와 pickups 를 표로 나타내면 위와 같다. 총 4개의 화물을 실을 수 있지만, 수거해야 하는 박스는 7개고 배달해야 하는 박스의 총 수는 7개이다. 즉 한 번으로는 배달을 할 수 없고, 중간에 차고지로 돌아와 다시 물건을 싣고 나가야 한다.

설명에 의하면 처음 출고때 상자 3개를 실어 출발하고, 5번 집까지 이동하며 4,5번 집에 배달을 마친다(이동거리 5)

다시 5번 집에서 물류창고로 돌아오며 4번 집에서 빈 박스 4개를 수거한다. (이동거리 5)

물류창고에서 4개의 화물을 실어서 3번집까지 이동하며 1,3번 집에 배달을 마친다(이동거리 3)

다시 물류창고로 돌아오며 2번집의 빈 박스 3개를 수거한다. (이동거리 3)

따라서 최소 이동거리는 16이 된다.

 

내가 생각한 문제의 핵심은, cap 개 만큼 배달 가능한 거리와 그 때 회수 가능한 빈 박스의 개수이다.

위 설명을 거꾸로 돌아도 같은 답이 나오긴 하지만, 처음 시작을 잘 설정해야 한다.

어짜피 마지막 집까지는 무조건 배달/수거 가 이루어져야 하는 상황이라면, 가장 먼 집의 배달/수거를 우선적으로 시행하는게 이동을 줄일 수 있다.

처음 작성한 코드는 while문을 사용하여, 배달/수거할 물건이 없을 때까지 조건을 설정하였다.

먼저 st 는 현재 누적 화물을 계산할 변수이다.

1. 이동거리 설정 

- 단순하게 range(n)을 역순으로 돌면서 마지막 집부터 탐색한다. 만약 배달이 필요하다면 break를 통해 건너띄고 배달이 필요하지 않다면 n 값을 1 감소 시키며 탐색을 계속한다.

2. 화물 배달

배달 또한 range(n)을 역순으로 돌면서 진행한다. 전체 화물을 다 배달 가능한 경우라면 전체 개수만큼 st에 더해주고 해당 집의 값은 0으로 만들어 준다. 만약 한번에 배달이 불가능한 경우라면 적재 가능한 만큼한 현재 요소에서 제거하고 종료한다.

 

3. 빈 박스 수거

다시 st = 0 으로 돌려주고, 배달과 마찬가지로 반복문을 이용하여 요소의 값을 치환한다.

 

그리고 마지막으로 answer의 n*2(왕복) 만큼 이동 거리를 누적 증가 시킨다.

결과는 이번에도 시간 초과이다.

n 값을 감소시켜 탐색범위를 줄여 나가기 때문에 큰 문제는 없을거라 생각했는데, 효율성 부분에서 걸리는 테케가 존재하는것 같다.

머리를 싸매고 고민하다가, 왜 이렇게 생각하지 못했는지 자신을 반성하게 되었다.

코드가 굉장히 간단해 보이지만, 굉장히 심오한 코드이다.

 

예제 5, 3, [5, 0, 5], [0, 1, 10]을 위 코드로 확인해보자.

 

먼저 배달 수거 수량을 확인할 변수를 선언해 준다.

이제 n 값을 기준으로 deliveries 와 pickups 배열을 역순으로 탐색하게 된다. i == 2

일단 배달/수거를 실시한다. 마지막 마을에 0/0이 아니라면 무조건 while문을 타게 된다. 즉, cnt 값이 증가한다. 이는 왕복으로 그 마을까지 배달을 했다는 뜻이다. 현재 st [-5,-10]

그리고 cap 만큼 값을 1회 회복시켜 준다. st [0, -5], cnt 1

값 둘다 0 미만 이므로 1회 더 회복시켜 준다. st[5,0] cnt 2

이제 while문을 탈출하고 answer 에 값을 전달한다. i+1 은 현재 마을 번호, 2 는 왕복 cnt 는 방문 횟수가 된다.

이제 i 가 1이 되었다.

 

다시  두 배열을 값을 st 의 요소에 빼주게 되면, [5, -1] 이 된다.

다시 while문을 돌고 st [10, 4] 가 된다.

그리고 answer 에 값을 추가한다.

 

이제 i == 0 이다. 마지막 순환이다.

deliveries[0] 에 의해 st [5,4] 가 되었다. while 문을 돌지 않는다.

여기서 중요한 점은 cnt 값이 0 이라는 점이다. 즉 answer 에 값이 추가되지 않는다.

즉, 앞서 배달때 처리가 가능하다는 점을 값을 증가 시켜서 처리 하였다.