Level 2/Lv2_48_택배 배달과 수거하기.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## [택배 배달과 수거하기](https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=python3)\n",
    "### 🔥 풀이"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 241008 TUE PM 10:52\n",
    "# return: 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리\n",
    "# 거리가 가장 먼 집부터 배달수거해야 최소 이동 거리를 구할 수 있음 => 그리디 알고리즘\n",
    "\n",
    "def solution(cap, n, deliveries, pickups):\n",
    "    \n",
    "    # (집의 거리, 배달 개수, 수거 개수)\n",
    "    idps = []\n",
    "    for i, (d, p) in enumerate(zip(deliveries, pickups), 1):\n",
    "        idps.append((i, d, p))\n",
    "    \n",
    "    # 현재 거리에서 얼만큼 배달수거했는지 저장하는 변수\n",
    "    delivery = 0\n",
    "    pickup = 0\n",
    "    \n",
    "    # 이동거리 합 계산\n",
    "    answer = 0\n",
    "\n",
    "    # stack의 .pop() 이용해서 가장 먼 집부터 가까운 집까지 순서대로 배달수거 진행\n",
    "    # 배달수거된 집은 stack에서 제거되므로 모든 집이 배달수거되면 while문 종료됨\n",
    "    while idps:\n",
    "        i, d, p = idps.pop()\n",
    "        \n",
    "        delivery += d\n",
    "        pickup += p\n",
    "        \n",
    "        # 현재 stack 기준으로 배달 or 수거가 이루어진 가장 먼 위치 인덱싱 => 거리 계산\n",
    "        # delivery < 0, pickup < 0인 경우: 추가 배달 가능\n",
    "        # ex. delivery = 3 => 3만큼 배달 완료\n",
    "        # ex. delivery = -3 => 3만큼 추가 배달 가능\n",
    "        \n",
    "        # 인덱싱 기준 다음 집(ex. i=5 => i=4)을 살펴보면서 d와 p를 더해도 0을 넘지 않으면\n",
    "        # 이전 집을 배달수거하면서 현재 집도 같이 배달수거 할 수 있는지 체크할 수 있음\n",
    "        while delivery > 0 or pickup > 0:\n",
    "            \n",
    "            # 최대 거리 인덱싱 후 이동거리 카운팅 \n",
    "            answer += i*2\n",
    "            \n",
    "            # 이동거리 카운팅했으니 돌아오는 길에 배달수거 추가로 얼마나 할 수 있는지 계산\n",
    "            # ex. i=5, delivery = 2, pickup = 0에서 cap = 4를 각각 빼주면\n",
    "            # delivery = -2, pickup = -4 => 각각 배달 2개, 수거 4개만큼의 여유분 존재한다는 것을 기록\n",
    "            delivery -= cap\n",
    "            pickup -= cap\n",
    "            \n",
    "    return answer"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}