당신은 일렬로 나열된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 함수를 완성해 주세요.
이 문제의 유형은 정확히는 모르겠지만 Greedy 알고리즘이 적합한 것 같습니다!
(배달과 수거 배열을 뒤에서부터 탐색하며 진행하기에 Greedy로 판단했습니다.)
배열의 크기(n)가 n ≤ 100,000 조건을 가지고 있기에 Stack 자료구조를 사용했습니다.
문제의 핵심은 배달 및 수거할 상자가 있는 인덱스만 stack에 넣어주어야 합니다.
배달과 수거를 각각 진행하며 이동 거리를 계산했습니다.
처음에 배달과 수거가 같이 완료된다고 생각했지만 테스트 케이스 3 ~ 20번을 충족하지 못해 아래 히든 테스트 케이스를 고려했습니다. 다음은 배달과 수거가 동시에 완료되지 않을 경우에 대한 테스트 케이스입니다 :
cap = 2, n = 3, deliveries = [1, 1, 0], pickups = [1, 1, 3], Return = 14
이 문제를 체감상 Lv.3라고 생각했는데, Lv.2라니.. 코딩 테스트 연습이 더 필요할 것 같습니다. 😥
문제 링크
문제 설명
당신은 일렬로 나열된
n
개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고,
i
번째 집은 물류창고에서 거리i
만큼 떨어져 있습니다. 또한i
번째 집은j
번째 집과 거리j - i
만큼 떨어져 있습니다. (1 ≤i
≤j
≤n
)트럭에는 재활용 택배 상자를 최대
cap
개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.다음은
cap
=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.배달 및 수거할 재활용 택배 상자 개수
16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수
cap
, 배달할 집의 개수를 나타내는 정수n
, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열deliveries
와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열pickups
가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.