Level 1/Lv1_41 체육복.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "56b7e372",
   "metadata": {},
   "source": [
    "# 체육복\n",
    "- `유형` 탐욕법(Greedy)\n",
    "\n",
    "\n",
    "- `문제 설명` \n",
    "\n",
    "\n",
    "점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.\n",
    "\n",
    "\n",
    "전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.\n",
    "\n",
    "\n",
    "- `제한 조건`\n",
    "    - 전체 학생의 수는 2명 이상 30명 이하입니다.\n",
    "    - 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.\n",
    "    - 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.\n",
    "    - 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.\n",
    "    - 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.\n",
    "\n",
    "\n",
    "- `입력`\n",
    "    - ex1) 5, [2, 4], [1, 3, 5]\n",
    "    - ex2) 5, [2, 4], [3]\n",
    "    - ex3) 3, [3], [1]\n",
    "\n",
    "\n",
    "- `출력`\n",
    "    - ex1) 5\n",
    "    - ex2) 4\n",
    "    - ex3) 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "68f7fe0b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-05-13T01:44:47.927177Z",
     "start_time": "2022-05-13T01:44:47.923429Z"
    }
   },
   "outputs": [],
   "source": [
    "# SOL 1)\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def solution(n, lost, reserve_ori):\n",
    "    reserve = sorted(Counter(reserve_ori) - Counter(lost))\n",
    "    \n",
    "    for i in set(reserve_ori)-set(reserve):\n",
    "        lost.remove(i) \n",
    "    lost.sort()\n",
    "    \n",
    "    for i in range(len(lost)):\n",
    "        if lost[i]-1 in reserve:\n",
    "            reserve.remove(lost[i]-1)\n",
    "            lost[i]=0\n",
    "        elif lost[i]+1 in reserve:\n",
    "            reserve.remove(lost[i]+1)\n",
    "            lost[i]=0\n",
    "            \n",
    "    while 0 in lost:\n",
    "        lost.remove(0)\n",
    "    \n",
    "    return n-len(lost)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "60321602",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-05-13T01:47:15.483057Z",
     "start_time": "2022-05-13T01:47:15.479288Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "4\n",
      "2\n",
      "4\n",
      "4\n"
     ]
    }
   ],
   "source": [
    "print(solution(5, [2, 4], [1, 3, 5]))\n",
    "print(solution(5, [2, 4], [3]))\n",
    "print(solution(3, [3], [1]))\n",
    "print(solution(5, [1, 2, 4], [2, 4, 5])) # testcase 5, 7, 12\n",
    "print(solution(5, [1, 2, 4], [2, 3, 4, 5])) # testcase 5, 7, 12"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}