LinkedList

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "2022_Mar_APR_LeetCode.ipynb",
      "provenance": [],
      "collapsed_sections": [
        "Zj63Amu81wo4",
        "OcLZGnV1TBVH",
        "0WW1bZ8K5W0V",
        "RdfDISw7rpjJ",
        "yjxNwbE_lLtU",
        "VHuU7fl3r0Ps",
        "pQ0rnJ2W1my6",
        "Mtsbggw9BPOB",
        "z9aPj8WhrXFC",
        "60woMsTnUy4G"
      ],
      "toc_visible": true,
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/minsuking/LeetCode_Practice/blob/master/LinkedList\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Introduction\n",
        "MeetUp Link\n",
        "\n",
        "https://meet.google.com/vku-dnyp-aen\n",
        "\n",
        "문제 출제 순서\n",
        "\n",
        "(Joseph) -> (Leo) -> Minsu -> Youngsu -> (Jinjoo) -> (Hanbit) -> jooho\n",
        "\n",
        "leokim2024@gmail.com\n",
        "\n",
        "terun707@gmail.com\n",
        "\n",
        "minsu.kim08@gmail.com\n",
        "\n",
        "(jinson355@gmail.com)\n",
        "\n",
        "(seongholee4@gmail.com)\n",
        "\n",
        "maran0119@gmail.com \n",
        "\n",
        "appleice4591@gmail.com\n",
        "\n",
        "2021 Amazon OA (SDE 1 105 Mins):\n",
        "Two Sum Variation: https://leetcode.com/discuss/interview-question/938809/amazon-oa-amazon-music-runtime#:~:text=Amazon%20music%20is%20working%20on,the%20songs%20from%20a%20list. *Lots of edge cases handling required to pass all test cases\n",
        "\n",
        "https://leetcode.com/discuss/interview-question/1488281/amazon-oa\n",
        "\n",
        "\n",
        "https://interviewing.io/recordings\n",
        "\n",
        "https://wiki.python.org/moin/TimeComplexity (Shared by Leo, TimeComplexity)\n",
        "\n",
        "https://seanprashad.com/leetcode-patterns/\n",
        "\n",
        "##. Amazon OA Solutions\n",
        "\n",
        "https://colab.research.google.com/drive/1n7AWBbPc9r9zF5qkMlCdaKZreoFz-M5Z?usp=sharing\n"
      ],
      "metadata": {
        "id": "v7RNp-CUvUos"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 02 2022\n",
        "\n",
        "17. Letter Combinations of a Phone Number\n",
        "\n",
        "https://leetcode.com/problems/letter-combinations-of-a-phone-number/\n"
      ],
      "metadata": {
        "id": "ADsm2Az4KoSd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "# Category : Backtracking\n",
        "# TC : O(4^N)\n",
        "class Solution:\n",
        "    def letterCombinations(self, digits: str) -> List[str]:\n",
        "        if len(digits)==0:\n",
        "            return []\n",
        "        map_ = {\"2\":\"abc\", \"3\":\"def\", \"4\":\"ghi\", \"5\":\"jkl\", \"6\":\"mno\", \"7\":\"pqrs\", \"8\":\"tuv\", \"9\":\"wxyz\"}\n",
        "        \n",
        "        def dfs(x, com):\n",
        "            if x == len(digits):\n",
        "                res.append(com)\n",
        "                return \n",
        "            for i in range(len(map_[digits[x]])):\n",
        "                com = com+map_[digits[x]][i]\n",
        "                dfs(x+1, com)\n",
        "                com = com[:-1]\n",
        "        res = []\n",
        "        dfs(0, \"\")\n",
        "        return res"
      ],
      "metadata": {
        "id": "bXalodvNrP4f"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def letterCombinations(self, digits: str) -> List[str]:\n",
        "        if not digits:\n",
        "            return []\n",
        "        dic = {}\n",
        "        dic['2'] = 'abc'\n",
        "        dic['3'] = 'def'\n",
        "        dic['4'] = 'ghi'\n",
        "        dic['5'] = 'jkl'\n",
        "        dic['6'] = 'mno'\n",
        "        dic['7'] = 'pqrs'\n",
        "        dic['8'] = 'tuv'\n",
        "        dic['9'] = 'wxyz'\n",
        "        \n",
        "        ans = []\n",
        "        def help(i, arr):\n",
        "            if i == len(digits):\n",
        "                ans.append(''.join(arr))\n",
        "                return\n",
        "            \n",
        "            for c in dic[digits[i]]:\n",
        "                arr.append(c)\n",
        "                help(i+1, arr)\n",
        "                arr.pop()\n",
        "        help(0,[])\n",
        "        return ans"
      ],
      "metadata": {
        "id": "MlqxhGtyrFlG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def letterCombinations(self, digits: str) -> List[str]:\n",
        "        _map = {\n",
        "            \"2\": [\"a\", \"b\", \"c\"],\n",
        "            \"3\": [\"d\", \"e\", \"f\"],\n",
        "            \"4\": [\"g\", \"h\", \"i\"],\n",
        "            \"5\": [\"j\", \"k\", \"l\"],\n",
        "            \"6\": [\"m\", \"n\", \"o\"],\n",
        "            \"7\": [\"p\", \"q\", \"r\", \"s\"],\n",
        "            \"8\": [\"t\", \"u\", \"v\"],\n",
        "            \"9\": [\"w\", \"x\", \"y\", \"z\"],\n",
        "        }\n",
        "        res = []\n",
        "        \n",
        "        def helper(arry, cur):\n",
        "            if cur and len(cur) == len(digits):\n",
        "                res.append(cur)\n",
        "                return\n",
        "            \n",
        "            for i, d in enumerate(arry):\n",
        "                for c in _map[d]:\n",
        "                    helper(arry[i+1:], cur+c)\n",
        "        \n",
        "        if digits:\n",
        "            helper(digits, \"\")\n",
        "                \n",
        "        return res"
      ],
      "metadata": {
        "id": "gi8VuYrkrqQV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "class Solution:\n",
        "    def letterCombinations(self, digits: str) -> List[str]:   \n",
        "        m = {\n",
        "            \"2\" : \"abc\",\n",
        "            \"3\" : \"def\",\n",
        "            \"4\" : \"ghi\",\n",
        "            \"5\" : \"jkl\",\n",
        "            \"6\" : \"mno\",\n",
        "            \"7\" : \"pqrs\",\n",
        "            \"8\" : \"tuv\",\n",
        "            \"9\" : \"wxyz\"\n",
        "        }\n",
        "             \n",
        "# Brute force  O(N^3)    \n",
        "#         res = [\"\"]\n",
        "        \n",
        "#         for i in digits:\n",
        "#             temp = []\n",
        "#             for j in m[i]:\n",
        "#                 for o in res:\n",
        "#                     temp.append(o+j)\n",
        "#             res = temp\n",
        "#         return res\n",
        "       \n",
        "        if digits == \"\":\n",
        "            return []\n",
        "        \n",
        "        words = []\n",
        "        def recursion(self, word, i):\n",
        "            if i >= len(digits):\n",
        "                words.append(word)\n",
        "                return word\n",
        "            \n",
        "            for digit in m[digits[i]]:\n",
        "                recursion(self, word + digit, i + 1)        \n",
        "        \n",
        "        recursion(self, \"\", 0)\n",
        "        return words"
      ],
      "metadata": {
        "id": "eMe1mTzWxX0O"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "class Solution:\n",
        "    def letterCombinations(self, digits: str) -> List[str]:\n",
        "        \n",
        "        def dfs(index, path):\n",
        "            \n",
        "            if len(path) == len(digits):\n",
        "                result.append(path)\n",
        "                return\n",
        "            \n",
        "            for i in range(index, len(digits)):\n",
        "                for j in letter[digits[i]]:\n",
        "                    dfs(i+1, path+j)\n",
        "        \n",
        "        if not digits:\n",
        "            return []\n",
        "        \n",
        "        letter = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}\n",
        "        result = []\n",
        "        \n",
        "        dfs(0,\"\")\n",
        "        \n",
        "        return result\n",
        "        "
      ],
      "metadata": {
        "id": "qcGTj1HOxw7g"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 03 2022\n",
        "\n",
        "1146. Snapshot Array\n",
        "\n",
        "https://leetcode.com/problems/snapshot-array/\n"
      ],
      "metadata": {
        "id": "Zj63Amu81wo4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "#Category : design, binary search\n",
        "#idea : \n",
        "# init : Definition of 2d list\n",
        "# set : After tying snap_id and val, append to array\n",
        "# snap : Increase the number of snap_id\n",
        "# get : Search for snap_id using binary search. Important Point: When finding, it can also be found when snap_id is larger than the stored snap_id.\n",
        "#       Case [\"SnapshotArray\",\"set\",\"snap\",\"snap\",\"snap\",\"get\",\"snap\",\"snap\",\"get\"] [[1],[0,15],[],[],[],[0,2],[],[],[0,0]]\n",
        "from collections import defaultdict\n",
        "class SnapshotArray:\n",
        "\n",
        "    def __init__(self, length: int):\n",
        "        self.snapsArray = []\n",
        "        self.snap_id = 0\n",
        "        for i in range(length):\n",
        "            self.snapsArray.append([])\n",
        "        \n",
        "    def set(self, index: int, val: int) -> None:\n",
        "        self.snapsArray[index].append([self.snap_id, val])\n",
        "        \n",
        "    def snap(self) -> int:\n",
        "        self.snap_id += 1\n",
        "        return self.snap_id -1\n",
        "\n",
        "    def get(self, index: int, snap_id: int) -> int:\n",
        "        l, r = 0, len(self.snapsArray[index])\n",
        "        #print(self.snapsArray[index])\n",
        "        while l < r:\n",
        "            mid = (l + r) // 2\n",
        "            if self.snapsArray[index][mid][0] > snap_id:\n",
        "                r = mid\n",
        "            else:\n",
        "                l = mid + 1\n",
        "        idx = l - 1\n",
        "        if idx < 0:\n",
        "            return 0\n",
        "        return self.snapsArray[index][idx][1]\n",
        "        \n",
        "\n",
        "\n",
        "# Your SnapshotArray object will be instantiated and called as such:\n",
        "# obj = SnapshotArray(length)\n",
        "# obj.set(index,val)\n",
        "# param_2 = obj.snap()\n",
        "# param_3 = obj.get(index,snap_id)"
      ],
      "metadata": {
        "id": "R_5r5zLKvXfW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class SnapshotArray:\n",
        "    def __init__(self, length: int):\n",
        "        self.length = length\n",
        "        self.dic =  collections.defaultdict(dict) # dic [index] [snap_id] = value at snap id\n",
        "        self.arr = [list() for _ in range(length)] # arr[index]  = [ snap_id0 , snap_id3  ... ]\n",
        "        self.snap_id = 0\n",
        "        \n",
        "    def set(self, index: int, val: int) -> None:\n",
        "        self.dic[index][self.snap_id] = val\n",
        "        if not self.arr[index] or self.arr[index][-1] != self.snap_id: # empty OR new snap_id for index\n",
        "            self.arr[index].append(self.snap_id)\n",
        "        #print(self.dic)\n",
        "        \n",
        "    def snap(self) -> int:\n",
        "        self.snap_id += 1\n",
        "        return self.snap_id-1\n",
        "\n",
        "    def get(self, index: int, snap_id: int) -> int:\n",
        "        if snap_id in self.dic[index]:\n",
        "            return self.dic[index][snap_id]\n",
        "        snap_id = bisect.bisect_left(self.arr[index], snap_id)\n",
        "        if snap_id-1 < 0: # snap_id = 0  ==> no item OR only larger snap_ids in array\n",
        "            return 0\n",
        "        #print(self.arr)\n",
        "        #print(index, snap_id-1)\n",
        "        return self.dic[index][   self.arr[index][snap_id-1]   ]"
      ],
      "metadata": {
        "id": "MFd1pN403bym"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "class SnapshotArray:\n",
        "\n",
        "    def __init__(self, length: int):\n",
        "        self.array = []\n",
        "        self.map = defaultdict(int)\n",
        "        self.i = 0\n",
        "\n",
        "    def set(self, index: int, val: int) -> None:\n",
        "        self.map[index] = val\n",
        "    \n",
        "    def snap(self) -> int:\n",
        "        self.array.append(self.map.copy())\n",
        "        self.i += 1\n",
        "        return self.i - 1\n",
        "        \n",
        "    def get(self, index: int, snap_id: int) -> int:\n",
        "        return self.array[snap_id][index]\n",
        "    "
      ],
      "metadata": {
        "id": "5352FDGP8Mgu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Leo \n",
        "class SnapshotArray:\n",
        "    def __init__(self, length: int):\n",
        "        #self.length = length\n",
        "        #self.arr = [0] * length  #initalize \n",
        "        self.snap_id = 0\n",
        "        self.snapshots = { i : {0:0} for i in range(length) }\n",
        "        \n",
        "    def set(self, index: int, val: int) -> None:\n",
        "        self.snapshots[index][self.snap_id] = val\n",
        "\n",
        "    def snap(self) -> int:\n",
        "        #self.snapshots[snap_id] = self.arr.copy()\n",
        "        self.snap_id += 1\n",
        "        return self.snap_id -1 \n",
        "\n",
        "    def get(self, index: int, snap_id: int) -> int:\n",
        "        while snap_id >0 and self.snapshots[index].get(snap_id) == None :\n",
        "            snap_id -= 1\n",
        "\n",
        "        return self.snapshots[index][snap_id]\n",
        "\n",
        "\n",
        " '''     self.snap =2\n",
        " idx.   {snap_id,val} \n",
        " 0      {0,0} -  { 1 , 3} - { 2, 1 }.. [0 , 3 ,1  ]\n",
        " 1.  ...{0,0} \n",
        " 2.     {0,0}.                \n",
        " '''\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "# Your SnapshotArray object will be instantiated and called as such:\n",
        "# obj = SnapshotArray(length)\n",
        "# obj.set(index,val)\n",
        "# param_2 = obj.snap()\n",
        "# param_3 = obj.get(index,snap_id)\n",
        "\n"
      ],
      "metadata": {
        "id": "eEb2x4zd8ugU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "class SnapshotArray:\n",
        "\n",
        "    def __init__(self, length: int):\n",
        "        self.snaps = {x:{0:0} for x in range(length)}\n",
        "        self.snap_id = 0\n",
        "\n",
        "    def set(self, index: int, val: int) -> None:\n",
        "        self.snaps[index][self.snap_id] = val\n",
        "     \n",
        "    def snap(self) -> int:\n",
        "        self.snap_id += 1\n",
        "        return self.snap_id - 1\n",
        "\n",
        "    def get(self, index: int, snap_id: int) -> int:\n",
        "        \n",
        "        while snap_id not in self.snaps[index] and snap_id > 0:\n",
        "            snap_id -= 1\n",
        "        return self.snaps[index][snap_id]\n",
        "\n",
        "    \n",
        "# Your SnapshotArray object will be instantiated and called as such:\n",
        "# obj = SnapshotArray(length)\n",
        "# obj.set(index,val)\n",
        "# param_2 = obj.snap()\n",
        "# param_3 = obj.get(index,snap_id)"
      ],
      "metadata": {
        "id": "pWrlIjhf9CeE"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 04 2022\n",
        "\n",
        "317 Shortest Distance from all buildings\n",
        "\n",
        "https://leetcode.com/problems/shortest-distance-from-all-buildings/"
      ],
      "metadata": {
        "id": "OcLZGnV1TBVH"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Leo's \n",
        "\n",
        "from collections import deque \n",
        "\n",
        "class Solution:\n",
        "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
        "        #0 = land \n",
        "        #1 = building \n",
        "        #2 = obs \n",
        "        \n",
        "        #loop, collect all building coordinates \n",
        "        #helper function -> calculate total distance \n",
        "        \n",
        "        #for all 0 coordinates in the grid, \n",
        "        #check all total distance \n",
        "        \n",
        "        if not grid or len(grid[0]) == 0:\n",
        "            return 0 \n",
        "        \n",
        "        \n",
        "        movements = {(0,1),(1,0),(-1,0),(0,-1)} # < -> ^ v \n",
        "        \n",
        "        rows,cols = len(grid), len(grid[0])\n",
        "        \n",
        "        distances = [ [0]*cols for _ in range(rows) ] \n",
        "        reach = [ [0]*cols for _ in range(rows) ] \n",
        "        buildingNums = 0 \n",
        "        \n",
        "        \n",
        "        def bfs(grid, distances, reach, rows, cols,r,c):\n",
        "            lv = 1 \n",
        "            visited = [ [0]*cols for _ in range(rows) ] \n",
        "            q = deque()\n",
        "            q.append( (r,c) )\n",
        "            while q:\n",
        "                x,y = q.popleft()\n",
        "                for dx,dy in movements:\n",
        "                    nx,ny = x + dx , y + dy \n",
        "                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 0 or visited[nx][ny]:\n",
        "                        continue \n",
        "                        \n",
        "                    q.append((nx,ny))\n",
        "                    visited[nx][ny] = True \n",
        "                    distances[nx][ny] += lv \n",
        "                    reach[nx][ny] += 1 \n",
        "                        \n",
        "                        \n",
        "                lv += 1\n",
        "        \n",
        "        \n",
        "        \n",
        "        for r in range(rows):\n",
        "            for c in range(cols):\n",
        "                #count buildings ... \n",
        "                bfs(grid, distances, reach, rows, cols , r ,c )\n",
        "                buildingNums+= 1 \n",
        "                \n",
        "                \n",
        "        \n",
        "        res = float('inf')\n",
        "        for i in range(rows):\n",
        "            for j in range(cols):\n",
        "                \n",
        "                if grid[i][j] == 0 and reach[i][j] == buildingNums:\n",
        "                    res = min( res, distances[i][j])\n",
        "        \n",
        "        return res if res != float('inf') else -1\n",
        "    "
      ],
      "metadata": {
        "id": "17ZDf7xsF3yT"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "from collections import deque\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
        "        def check_index(r, c):\n",
        "            if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]):\n",
        "                return False\n",
        "            return True\n",
        "\n",
        "        def bfs(row, col):\n",
        "            nonlocal houses\n",
        "\n",
        "            reached = 0\n",
        "            total_distance = 0\n",
        "            visited = set()\n",
        "            visited.add((row, col))\n",
        "            que = deque([(row, col, 0)])\n",
        "\n",
        "            while que and reached < houses:\n",
        "                cur_row, cur_col, distance = que.popleft()\n",
        "                if grid[cur_row][cur_col] == 1:\n",
        "                    reached += 1\n",
        "                    total_distance += distance\n",
        "                    continue\n",
        "\n",
        "                for d in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
        "                    new_row = cur_row + d[0]\n",
        "                    new_col = cur_col + d[1]\n",
        "                    if (new_row, new_col) not in visited and check_index(new_row, new_col) and grid[new_row][new_col] != 2:\n",
        "                        visited.add((new_row, new_col))\n",
        "                        que.append((new_row, new_col, distance + 1))\n",
        "\n",
        "            if reached < houses:\n",
        "                for r, c in visited:\n",
        "                    if grid[r][c] == 0:\n",
        "                        grid[r][c] = 2\n",
        "                return float('inf')\n",
        "            \n",
        "            return total_distance\n",
        "\n",
        "        rows = len(grid)\n",
        "        cols = len(grid[0])\n",
        "\n",
        "        houses = 0\n",
        "        res = float('inf')\n",
        "\n",
        "        for r in range(rows):\n",
        "            for c in range(cols):\n",
        "                if grid[r][c] == 1:\n",
        "                    houses += 1\n",
        "\n",
        "        for r in range(rows):\n",
        "            for c in range(cols):\n",
        "                if grid[r][c] == 0:\n",
        "                    res = min(res, bfs(r, c))\n",
        "\n",
        "        return res if res != float('inf') else -1\n"
      ],
      "metadata": {
        "id": "j1ngbjRbIJLc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
        "        dirs = [[1,0],[0,1],[-1,0],[0,-1]]\n",
        "        m = len(grid)\n",
        "        n = len(grid[0])\n",
        "        \n",
        "        building_cnt = 0\n",
        "        for i in range(m):\n",
        "            for j in range(n):\n",
        "                if grid[i][j] == 1:\n",
        "                    building_cnt += 1\n",
        "                    ans = math.inf\n",
        "                    deq = collections.deque()\n",
        "                    \n",
        "                    for x,y in dirs:\n",
        "                        new_x = i+x\n",
        "                        new_y = j+y\n",
        "                        if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] <= -1000000 * (building_cnt-1): # the cell should be visited buildings-1 times\n",
        "                            deq.append((new_x,new_y,1))\n",
        "                    \n",
        "                    while deq:\n",
        "                        a,b,cost = deq.popleft()\n",
        "                        if grid[a][b] < -1000000 * (building_cnt): # already visited for grid[i][j] case\n",
        "                            continue\n",
        "                        grid[a][b] -= 1000000 # visited time\n",
        "                        grid[a][b] -= cost # cost\n",
        "                        \n",
        "                        ans = min(ans, (-grid[a][b]) % 1000000)     # new cost\n",
        "                        \n",
        "                        for x,y in dirs:\n",
        "                            new_x = a+x\n",
        "                            new_y = b+y\n",
        "                            if 0 <= new_x < m and 0 <= new_y < n and -1000000 * (building_cnt) < grid[new_x][new_y] <= -1000000 * (building_cnt-1): # the cell should be visited buildings-1 times\n",
        "                                deq.append((new_x,new_y,cost+1))\n",
        "        \n",
        "        return ans if ans != math.inf else -1"
      ],
      "metadata": {
        "id": "5D4hPevkIbmA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "class Solution:\n",
        "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
        "        \n",
        "        m, n = len(grid), len(grid[0])\n",
        "        maps = {0:[], 1:[]}\n",
        "        \n",
        "        for r in range(m):\n",
        "            for c in range(n):\n",
        "                if grid[r][c] == 0:\n",
        "                    maps[0].append((r,c))\n",
        "                elif grid[r][c] == 1:\n",
        "                    maps[1].append((r,c))\n",
        "        \n",
        "        # Hashmap for stroing distance from each building to empty land\n",
        "        distances = {x:{y:float('inf') for y in maps[1]} for x in maps[0]}\n",
        "\n",
        "        def bfs(r,c):\n",
        " \n",
        "            q = collections.deque([(r,c,0)])\n",
        "            visited = set((r,c))\n",
        "            \n",
        "            while q:\n",
        "                cur_r, cur_c, d = q.popleft()\n",
        "                \n",
        "                for nr, nc in [[cur_r-1, cur_c], [cur_r+1, cur_c], [cur_r, cur_c-1], [cur_r, cur_c+1]]:\n",
        "                    \n",
        "                    if (nr,nc) in distances and (nr,nc) not in visited:\n",
        "                        visited.add((nr,nc))\n",
        "                        distances[(nr,nc)][(r,c)] = d + 1\n",
        "                        q.append([nr, nc, d+1])\n",
        "        \n",
        "        \n",
        "        res = float('inf')\n",
        "        \n",
        "        for r,c in maps[1]:\n",
        "            bfs(r,c)\n",
        "\n",
        "        for d in distances.values():\n",
        "            res = min(res, sum(d.values()))\n",
        "        \n",
        "        return res if res < float('inf') else -1\n",
        "        "
      ],
      "metadata": {
        "id": "EX8MT6jlrS5i"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 07 2022\n",
        "\n",
        "2096. Step-By-Step Directions From a Binary Tree Node to Another\n",
        "\n",
        "https://leetcode.com/problems/step-by-step-directions-from-a-binary-tree-node-to-another/"
      ],
      "metadata": {
        "id": "0WW1bZ8K5W0V"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#Idea : DFS로 startValue와 destValue의 경로를 찾는다. start의 경로 뒤에 dest 까지의 경로를 붙인다. \n",
        "#        ※ destValue를 찾을땐 찾고나서 경로가 reverse가 되어야되기 때문에 index 0 번째에 값을 넣어준다.\n",
        "#           list를 사용한다면 insert(0, L or R), deque 를 사용한다면 appendleft사용해서 넣기 TC : O(1)\n",
        "#TC : O(n), SC : O(N)\n",
        "\n",
        "# Definition for a binary tree node.\n",
        "# class TreeNode:\n",
        "#     def __init__(self, val=0, left=None, right=None):\n",
        "#         self.val = val\n",
        "#         self.left = left\n",
        "#         self.right = right\n",
        "from collections import deque\n",
        "class Solution:\n",
        "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
        "        def dfs(root, startValue, destValue):\n",
        "            if root == None:\n",
        "                return 0\n",
        "            \n",
        "            res = 0\n",
        "            if root.val == startValue or root.val == destValue:\n",
        "                res += root.val\n",
        "            \n",
        "            left = dfs(root.left, startValue, destValue)\n",
        "            right = dfs(root.right, startValue, destValue)\n",
        "            res += left + right\n",
        "            \n",
        "            if left == startValue or right == startValue:\n",
        "                start.append('U')\n",
        "            if left == destValue:\n",
        "                dest.appendleft('L')\n",
        "            if right == destValue:\n",
        "                dest.appendleft('R')\n",
        "            \n",
        "            return res\n",
        "        \n",
        "        #appendleft (TC : O(1)) 때문에 deque사용을했는데 start는 list를 사용해도 상관은 없을듯\n",
        "        start = deque()\n",
        "        dest = deque()\n",
        "        dfs(root, startValue, destValue)\n",
        "        start.extend(dest)\n",
        "        return \"\".join(start)"
      ],
      "metadata": {
        "id": "mmXXSsoE7JbR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH\n",
        "# Definition for a binary tree node.\n",
        "# class TreeNode:\n",
        "#     def __init__(self, val=0, left=None, right=None):\n",
        "#         self.val = val\n",
        "#         self.left = left\n",
        "#         self.right = right\n",
        "class Solution:\n",
        "    def getDirections(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:\n",
        "        \n",
        "        graph = collections.defaultdict(list)\n",
        "        q = collections.deque([root])\n",
        "        \n",
        "        \n",
        "        while q:\n",
        "            node = q.popleft()\n",
        "            \n",
        "            if node.left:\n",
        "                graph[node.left.val].append((node.val, 'U'))\n",
        "                graph[node.val].append((node.left.val, 'L'))\n",
        "                \n",
        "                q.append(node.left)\n",
        "                \n",
        "            if node.right:\n",
        "                graph[node.right.val].append((node.val, 'U'))\n",
        "                graph[node.val].append((node.right.val, 'R'))\n",
        "                \n",
        "                q.append(node.right)\n",
        "        \n",
        "        \n",
        "        q = collections.deque([(startValue, \"\")])\n",
        "        visited = set()\n",
        "        \n",
        "        while q:\n",
        "            cur_val, cur_path = q.popleft()\n",
        "            \n",
        "            if cur_val in visited:\n",
        "                continue\n",
        "            \n",
        "            visited.add(cur_val)\n",
        "            \n",
        "            if cur_val == destValue:\n",
        "                return cur_path\n",
        "            else:\n",
        "                for next_val,next_path in graph[cur_val]:\n",
        "                    if next_val not in visited:\n",
        "                        q.append((next_val, cur_path+next_path))\n",
        "        "
      ],
      "metadata": {
        "id": "X-iteuiSUrXm"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 23 2022\n",
        "\n",
        "380. Insert Delete GetRandom O(1)\n",
        "\n",
        "https://leetcode.com/problems/insert-delete-getrandom-o1/"
      ],
      "metadata": {
        "id": "RdfDISw7rpjJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "from collections import defaultdict\n",
        "class RandomizedSet:\n",
        "\n",
        "    def __init__(self):\n",
        "        self.repository = dict()\n",
        "\n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val in self.repository:\n",
        "            return False\n",
        "        self.repository[val] = 1\n",
        "        return True\n",
        "    \n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val in self.repository:\n",
        "            del self.repository[val]\n",
        "            return True\n",
        "        return False\n",
        "\n",
        "    def getRandom(self) -> int:\n",
        "        keyList = list(self.repository.keys())\n",
        "        return random.choice(keyList)"
      ],
      "metadata": {
        "id": "x5vzj49VruN0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe's Code\n",
        "class RandomizedSet:\n",
        "\n",
        "    def __init__(self):\n",
        "        self._set = {}\n",
        "        self.values = []\n",
        "        \n",
        "\n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val in self._set:\n",
        "            return False\n",
        "        self._set[val] = len(self.values)\n",
        "        self.values.append(val)\n",
        "        return True\n",
        "\n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val not in self._set:\n",
        "            return False\n",
        "        i = self._set[val]\n",
        "        self._set[self.values[-1]] = i\n",
        "        self.values[i], self.values[-1] = self.values[-1], self.values[i]\n",
        "        del self._set[val]\n",
        "        self.values.pop()\n",
        "        return True\n",
        "\n",
        "    def getRandom(self) -> int:\n",
        "        return random.choice(self.values)  \n",
        "\n",
        "##############################################\n",
        "\n",
        "class RandomizedSet:\n",
        "\n",
        "    def __init__(self):\n",
        "        self._set = set()\n",
        "        \n",
        "\n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val in self._set:\n",
        "            return False\n",
        "        self._set.add(val)\n",
        "        return True\n",
        "\n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val not in self._set:\n",
        "            return False\n",
        "        self._set.remove(val)\n",
        "        return True\n",
        "\n",
        "    def getRandom(self) -> int:\n",
        "        return random.choice(list(self._set))  "
      ],
      "metadata": {
        "id": "TKTjUpAoElN4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "class RandomizedSet:\n",
        "    class RandomizedSet:\n",
        "    def __init__(self):\n",
        "        self.set = {}\n",
        "        self.vals = []\n",
        "        \n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val in self.set and self.set[val] != '@':\n",
        "            return False\n",
        "        self.set[val] = len(self.vals)\n",
        "        self.vals.append(val)\n",
        "        return True\n",
        "\n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val in self.set and self.set[val] != '@':\n",
        "                ix = self.set[val]\n",
        "                temp = self.vals[-1]\n",
        "            \n",
        "                self.set[temp] = ix\n",
        "                self.vals[ix] = temp\n",
        "            \n",
        "                self.vals.pop()\n",
        "                self.set[val] = '@'\n",
        "                return True\n",
        "        return False\n",
        "\n",
        "    def getRandom(self) -> int:\n",
        "        return random.choice(self.vals)\n"
      ],
      "metadata": {
        "id": "4_V5MAkeYroh"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Jinjoo \n",
        "\"\"\" \n",
        "Idea \n",
        "\n",
        "Insert, Remove can be done normally, using the library set fns. \n",
        "\n",
        "getRandom => cannot use set lib. fns. \n",
        "appr. \n",
        "- use arr that holds the elements in the set \n",
        "- use rand w range (0~len(arr)) to select an element by ind from the arr \n",
        "\n",
        "Problem : \n",
        "copying all the elements of set into the arr => O(n) \n",
        "\n",
        "Solution : \n",
        "add and delete simultaenously as operation is done on set. \n",
        "    - problem: delete an elem from arr => x O(1)\n",
        "    - solution: need to keep a pointer for the pos of els in the arr \n",
        "        - extra data to store => dictionary. (x tuple, arr in set, you cannot use it afaik)\n",
        "\n",
        "\"\"\"\n",
        "import random \n",
        "\n",
        "class RandomizedSet:\n",
        "\n",
        "    def __init__(self):\n",
        "        # k: num, v: ind (of the el in the arr)\n",
        "        self.rand_set = {} \n",
        "        self.arr = [] \n",
        "\n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val in self.rand_set: \n",
        "            return False \n",
        "        \n",
        "        self.arr.append(val) \n",
        "        self.rand_set[val] = len(self.arr) - 1 # store the ind as the val. \n",
        "        return True \n",
        "\n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val in self.rand_set: \n",
        "            ind = self.rand_set[val] \n",
        "            \n",
        "            # swap the element, so no need for shifting. \n",
        "            el_to_swap = self.arr[-1]\n",
        "            self.arr[ind], self.rand_set[el_to_swap] = el_to_swap, ind\n",
        "            self.arr.pop() \n",
        "            self.rand_set.pop(val)\n",
        "            return True \n",
        "        \n",
        "        \n",
        "        return False \n",
        "\n",
        "    # 5 2 3 => 5/2/3 (same prob.)\n",
        "    # pick an el from an array 5 2 3, by ind. (where ind ranges from 0-2)\n",
        "    def getRandom(self) -> int:\n",
        "        length = len(self.rand_set)\n",
        "        rand_num = random.randint(0, length-1)\n",
        "\n",
        "        return self.arr[rand_num]\n",
        "        "
      ],
      "metadata": {
        "id": "pVIbJRfdd9u-"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH  17/19 passed\n",
        "\n",
        "class RandomizedSet:\n",
        "\n",
        "    def __init__(self):\n",
        "        self.set = set()\n",
        "        \n",
        "    def insert(self, val: int) -> bool:\n",
        "        if val not in self.set:\n",
        "            self.set.add(val)\n",
        "            return True\n",
        "        return False\n",
        "\n",
        "    def remove(self, val: int) -> bool:\n",
        "        if val in self.set:\n",
        "            self.set.remove(val)\n",
        "            return True\n",
        "        return False\n",
        "\n",
        "    def getRandom(self) -> int:\n",
        "        a = self.set.pop()\n",
        "        self.set.add(a)\n",
        "        return a\n",
        "# Your RandomizedSet object will be instantiated and called as such:\n",
        "# obj = RandomizedSet()\n",
        "# param_1 = obj.insert(val)\n",
        "# param_2 = obj.remove(val)\n",
        "# param_3 = obj.getRandom()"
      ],
      "metadata": {
        "id": "Qp1ngXPUfroI"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 24 2022\n",
        "\n",
        "230. Kth Smallest Element in a BST\n",
        "\n",
        "https://leetcode.com/problems/kth-smallest-element-in-a-bst/"
      ],
      "metadata": {
        "id": "yjxNwbE_lLtU"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#Idea : BST의 특성을 생각하여 left부터 탐색을 하여 가장 왼쪽 노드(가장 작은 숫자)를 찾은 후 k 만큼 -하여 k가 0이 되었을때가 k번째 숫자.\n",
        "\n",
        "#TC : O(longN + k), #SC : O(N)\n",
        "class Solution:\n",
        "    k = -inf\n",
        "    res = 0\n",
        "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
        "        if self.k == -inf:\n",
        "            self.k = k\n",
        "        if root == None or self.k < 0 :\n",
        "            return None\n",
        "        self.kthSmallest(root.left, k)\n",
        "        self.k -= 1\n",
        "        if self.k == 0 :\n",
        "            self.res = root.val\n",
        "        self.kthSmallest(root.right, k)\n",
        "        return self.res"
      ],
      "metadata": {
        "id": "taZWYE2rMFbi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit \n",
        "# recursion, inorder traversal using a helper method \n",
        "class Solution:\n",
        "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
        "        \n",
        "        self.cur = 1\n",
        "        self.ans = None\n",
        "    \n",
        "        def helper(node):\n",
        "            if not node or self.ans:\n",
        "                return \n",
        "            helper(node.left)\n",
        "            if self.cur == k:\n",
        "                self.ans = node.val \n",
        "            self.cur += 1\n",
        "            helper(node.right)\n",
        "        \n",
        "        helper(root)\n",
        "        return self.ans"
      ],
      "metadata": {
        "id": "WJE4N-dWhmRN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:\n",
        "        stack = []\n",
        "        node = root\n",
        "        while node or stack:\n",
        "            while node:\n",
        "                stack.append(node)\n",
        "                node = node.left\n",
        "            node = stack.pop()\n",
        "            k -= 1\n",
        "            if k < 1:\n",
        "                break\n",
        "            node = node.right\n",
        "        return node.val"
      ],
      "metadata": {
        "id": "dOf5J2A5lyYf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 25 2022\n",
        "\n",
        "979. Distribute Coins in Binary Tree\n",
        "\n",
        "https://leetcode.com/problems/distribute-coins-in-binary-tree/"
      ],
      "metadata": {
        "id": "VHuU7fl3r0Ps"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#YS\n",
        "class Solution:\n",
        "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
        "        ans = 0\n",
        "        def dfs(node):\n",
        "            if not node:\n",
        "                return 0\n",
        "            \n",
        "            left = dfs(node.left)\n",
        "            right = dfs(node.right)\n",
        "            \n",
        "            val = left + right + node.val - 1\n",
        "            \n",
        "            nonlocal ans\n",
        "            ans += abs(val)\n",
        "            \n",
        "            return val\n",
        "        dfs(root)\n",
        "        return ans"
      ],
      "metadata": {
        "id": "sYQHacjex0u5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "class Solution:\n",
        "    res = 0\n",
        "    def distributeCoins(self, root: TreeNode) -> int:\n",
        "        def dfs(root):\n",
        "            if root==None:\n",
        "                return 0\n",
        "            if root.left == None and root.right == None and root.val > 1:\n",
        "                return root.val - 1\n",
        "            left = dfs(root.left)\n",
        "            right = dfs(root.right)\n",
        "            self.res += abs(left) + abs(right)\n",
        "            return left + right + root.val -1 \n",
        "        dfs(root)\n",
        "        return self.res"
      ],
      "metadata": {
        "id": "K97_0l2ZuDUC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
        "        res = 0\n",
        "        \n",
        "        def dfs(node):\n",
        "            if not node:\n",
        "                return 0\n",
        "            nonlocal res\n",
        "            diff = node.val + dfs(node.left) + dfs(node.right) - 1\n",
        "            res += abs(diff)\n",
        "            \n",
        "            return diff\n",
        "        \n",
        "        dfs(root)\n",
        "        return res"
      ],
      "metadata": {
        "id": "medfc-W4vivE"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH\n",
        "class Solution:\n",
        "    def distributeCoins(self, root: Optional[TreeNode]) -> int:\n",
        "        self.moves = 0\n",
        "        def dfs(node):\n",
        "            if not node: \n",
        "                return 0\n",
        "            left, right = dfs(node.left), dfs(node.right)\n",
        "            self.moves += abs(left) + abs(right)\n",
        "            return node.val + left + right - 1\n",
        "\n",
        "        dfs(root)\n",
        "        return self.moves"
      ],
      "metadata": {
        "id": "2yUFmAJUxDHJ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 26 2022\n",
        "2055. Plates Between Candles \n",
        "https://leetcode.com/problems/plates-between-candles/"
      ],
      "metadata": {
        "id": "pQ0rnJ2W1my6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#YS\n",
        "class Solution:\n",
        "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
        "        n = len(s)\n",
        "        star_cnt = [-1] * n #  key=index of bar : value= # of star from start to this bar\n",
        "        next_bar = [-1] * n #  key=index of bar,star : value= index of next bar (if index=bar , value = current bar)\n",
        "        prev_bar = [-1] * n #  key=index of bar,star : value= index of prev bar ''\n",
        "        cnt = 0\n",
        "        prev = -1\n",
        "        \n",
        "        start_index = 0\n",
        "        for i,c in enumerate(s):\n",
        "            if c == '*':\n",
        "                cnt += 1\n",
        "                prev_bar[i] = prev\n",
        "            else: # '|'\n",
        "                star_cnt[i] = cnt\n",
        "                \n",
        "                for j in range(start_index, i+1):\n",
        "                    next_bar[j] = i\n",
        "                prev_bar[i] = i\n",
        "                prev = i\n",
        "                start_index = i+1\n",
        "                \n",
        "        ans = []\n",
        "        for s, e in queries:\n",
        "            next_bar_index = next_bar[s]\n",
        "            prev_bar_index = prev_bar[e]\n",
        "            #print( next_bar_index ,  prev_bar_index)\n",
        "            if  next_bar_index != -1 and prev_bar_index != -1  and next_bar_index   <  prev_bar_index:\n",
        "                ans.append(star_cnt[prev_bar_index] - star_cnt[next_bar_index])\n",
        "            else:\n",
        "                ans.append(0)\n",
        "        #print(star_cnt)\n",
        "        #print(next_bar)\n",
        "        #print(prev_bar)\n",
        "        return ans"
      ],
      "metadata": {
        "id": "puYJuwnZ6mdx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH\n",
        "class Solution:\n",
        "    def platesBetweenCandles(self, s: str, queries: List[List[int]]) -> List[int]:\n",
        "        \n",
        "        res = []\n",
        "        dp = [0]*len(s)\n",
        "        candle = []\n",
        "        for i,c in enumerate(s):\n",
        "            if c == '|': candle.append(i)\n",
        "            if c == '*':\n",
        "                dp[i] = dp[i-1] + 1\n",
        "            else:\n",
        "                dp[i] = dp[i-1]\n",
        "                \n",
        "        \n",
        "        for query in queries:   \n",
        "            \n",
        "            l = bisect_left(candle, query[0])\n",
        "            r = bisect_right(candle, query[1]) - 1\n",
        "            temp = 0\n",
        "\n",
        "            if l <= r:\n",
        "                temp = dp[candle[r]] - dp[candle[l]]\n",
        "\n",
        "            res.append(temp)\n",
        "            \n",
        "        return res\n"
      ],
      "metadata": {
        "id": "7TJOhbg18V9p"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 28 2022\n",
        "1293. Shortest Path in a Grid with Obstacles Elimination\n",
        "\n",
        "https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/"
      ],
      "metadata": {
        "id": "Mtsbggw9BPOB"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Minsu's code\n",
        "# BFS + PriorityQueue\n",
        "# Idea : pq 의 compare 기준을 count로 잡고 push하면서 min값으로 정렬\n",
        "#        방문을 했을때 장애물이 없으면 0, 장애물이 있으면 1증가, 증가값이 최대 k까지\n",
        "\n",
        "from queue import PriorityQueue\n",
        "class Solution:\n",
        "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
        "        class Data:\n",
        "            def __init__(self, x, y, k, count):\n",
        "                self.x = x\n",
        "                self.y = y\n",
        "                self.k = k\n",
        "                self.count = count\n",
        "            \n",
        "            def __lt__(self, other):\n",
        "                return self.count < other.count\n",
        "        \n",
        "        pq = PriorityQueue()\n",
        "        pq.put(Data(0,0,0,0))\n",
        "        dirs = ((0,1),(0,-1),(1,0),(-1,0))\n",
        "        n, m = len(grid), len(grid[0])\n",
        "        visited = [[inf] * m for _ in range(n)]\n",
        "        \n",
        "        visited[0][0] = 0\n",
        "        while not pq.empty():\n",
        "            data = pq.get()\n",
        "            print(data.x , data.y , data.k , data.count)\n",
        "            if data.x == n-1 and data.y == m-1:\n",
        "                return data.count\n",
        "            for d in dirs:\n",
        "                dx = data.x + d[0]\n",
        "                dy = data.y + d[1]\n",
        "                if dx >=0 and dx < n and dy >= 0 and dy < m and (visited[dx][dy] > data.k + grid[dx][dy]):\n",
        "                    if grid[dx][dy]==0 :\n",
        "                        visited[dx][dy] = data.k + grid[dx][dy]\n",
        "                        pq.put(Data(dx, dy, data.k + grid[dx][dy], data.count + 1))\n",
        "                    if grid[dx][dy]==1 and data.k + 1 <= k :\n",
        "                        visited[dx][dy] = data.k + grid[dx][dy]\n",
        "                        pq.put(Data(dx, dy, data.k + grid[dx][dy] , data.count +1))\n",
        "        return -1\n",
        "                    \n",
        "\n",
        "#dfs + memoization  \n",
        "#TLE or WA\n",
        "#방문횟수를 조건을 걸면 TLE, 조건을 빼면 WA\n",
        "#tricky한 케이스가 있는듯... \n",
        " class Solution:\n",
        "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
        "        dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
        "        n = len(grid)\n",
        "        m = len(grid[0])\n",
        "        memo = dict()\n",
        "        def dfs(x, y, n, m, k, count, res):\n",
        "            if x==n-1 and y==m-1:\n",
        "                #if (x,y,k) in memo:\n",
        "                #    memo[(x,y,k)] = min(memo[(x,y,k)], count)\n",
        "                #else:\n",
        "                memo[(x,y,k)] = count\n",
        "                return memo[(x,y,k)]\n",
        "            \n",
        "            if (x,y,k) in memo:\n",
        "                return memo[(x,y,k)]\n",
        "            \n",
        "            visited[x][y]=True\n",
        "            for d in dirs:\n",
        "                dx = x + d[0]\n",
        "                dy = y + d[1]\n",
        "                flag = False\n",
        "                if dx >= 0 and dx < n and dy >=0 and dy < m and visited[dx][dy] == False:\n",
        "                    if k > 0 and grid[dx][dy]==1:\n",
        "                        res = min(res, dfs(dx, dy, n, m, k-1, count+1, res))\n",
        "                    if grid[dx][dy]==0:\n",
        "                        res = min(res, dfs(dx, dy, n, m, k, count + 1, res))\n",
        "            visited[x][y]=False\n",
        "            #if (x,y,k) in memo:\n",
        "            #    memo[(x,y,k)] = min(res, memo[(x,y,k)])\n",
        "            #else:\n",
        "            memo[(x,y,k)] = res\n",
        "            return memo[(x,y,k)]\n",
        "        \n",
        "        visited = [[False] * m for _ in range(n)]\n",
        "        res = dfs(0, 0, n, m, k, 0, inf)\n",
        "        return -1 if res == inf else res   \n"
      ],
      "metadata": {
        "id": "tGSsB0mRN46y"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH\n",
        "# BFS\n",
        "class Solution:\n",
        "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
        "        \n",
        "        row, col = len(grid), len(grid[0])\n",
        "        \n",
        "        if row == 1 and col == 1:\n",
        "            return 0\n",
        "        \n",
        "        coordinate = (0,k,0,0)\n",
        "        q = collections.deque([coordinate])\n",
        "        visited =set([(k,0,0)])\n",
        "        \n",
        "        while q:\n",
        "            \n",
        "            steps, curr_k, p_row, p_col = q.popleft()\n",
        "            \n",
        "            for i, j in [(0,1), (1,0), (-1,0), (0, -1)]:\n",
        "                n_row, n_col = p_row + i, p_col + j\n",
        "                \n",
        "                if 0 <= n_row < row and 0 <= n_col < col:\n",
        "                    \n",
        "                    if n_row == (row-1) and n_col == (col-1):\n",
        "                        return steps + 1\n",
        "                    \n",
        "                    if grid[n_row][n_col] == 1 and curr_k > 0 and (curr_k -1, n_row, n_col) not in visited:\n",
        "                        visited.add((curr_k -1, n_row, n_col))\n",
        "                        q.append((steps+1, curr_k-1, n_row, n_col))\n",
        "                \n",
        "                    if grid[n_row][n_col] == 0 and (curr_k, n_row, n_col) not in visited:\n",
        "                        visited.add((curr_k, n_row, n_col))\n",
        "                        q.append((steps+1, curr_k, n_row, n_col))\n",
        "            \n",
        "        return -1"
      ],
      "metadata": {
        "id": "rQe52lopQczL"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Hanbit\n",
        "class Solution:\n",
        "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
        "        q = deque([[0,0,k,0]])\n",
        "        visited = set()\n",
        "        d = [[1,0], [-1,0], [0,1], [0,-1]]\n",
        "        \n",
        "        while q:\n",
        "            \n",
        "            x,y,k_,steps = q.popleft()\n",
        "            \n",
        "            if (x,y,k_) in visited or k_ < 0: \n",
        "                continue\n",
        "            \n",
        "            print(x,y,k_,steps)\n",
        "            if x == len(grid)- 1 and y == len(grid[0]) - 1:\n",
        "                return steps\n",
        "            \n",
        "            visited.add((x,y,k_))\n",
        "\n",
        "            if grid[x][y] == 1:\n",
        "                k_ = k_ - 1\n",
        "      \n",
        "            for i, j in d:\n",
        "                x_ = x + i\n",
        "                y_ = y + j\n",
        "                if -1 < x_ < len(grid) and -1 < y_ < len(grid[0]):\n",
        "                    q.append((x_, y_, k_, steps+1))     \n",
        "        return -1"
      ],
      "metadata": {
        "id": "qlUo1xESSrYP"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "from collections import deque\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def shortestPath(self, grid: List[List[int]], k: int) -> int:\n",
        "        rows = len(grid)\n",
        "        cols = len(grid[0])\n",
        "        target = (rows-1, cols-1)\n",
        "        \n",
        "        if k >= rows+cols-2:\n",
        "            return rows+cols-2\n",
        "        \n",
        "        q = deque([(0, (0, 0, k))])\n",
        "        visited = set()\n",
        "        visited.add((0, 0, k))\n",
        "        \n",
        "        while q:\n",
        "            step, (r, c, k) = q.popleft()\n",
        "            if (r, c) == target:\n",
        "                return step\n",
        "            \n",
        "            for nr, nc in [(r-1, c), (r, c-1), (r+1, c), (r, c+1)]:\n",
        "                if nr < 0 or nr >= rows or nc < 0 or nc >= cols:\n",
        "                    continue\n",
        "                \n",
        "                _k = k - grid[nr][nc]\n",
        "                \n",
        "                if _k >= 0 and (nr, nc, _k) not in visited:\n",
        "                    visited.add((nr, nc, _k))\n",
        "                    q.append((step+1, (nr, nc, _k)))\n",
        "        return -1"
      ],
      "metadata": {
        "id": "PzxJLeIFX3tR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 29 2022\n",
        "\n",
        "###Array\n",
        "\n",
        "1. https://leetcode.com/problems/product-of-array-except-self/\n",
        "\n",
        "2. https://leetcode.com/problems/maximum-product-subarray/"
      ],
      "metadata": {
        "id": "z9aPj8WhrXFC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit \n",
        "# 238. Product of Array Except Self\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
        "        \n",
        "        from_left = [1]\n",
        "        from_right = [1] * len(nums)\n",
        "        res = [1] * len(nums)\n",
        "        \n",
        "        for i in range(len(nums)-1):\n",
        "            from_left.append(from_left[i] * nums[i])\n",
        "        \n",
        "        [n, n, n, n, 1]\n",
        "\n",
        "        for i in reversed(range(1, len(nums))):\n",
        "            from_right[i-1] = from_right[i] * nums[i]\n",
        "                   \n",
        "        for i in range(len(nums)):\n",
        "            res[i] = from_left[i] * from_right[i]\n",
        "            \n",
        "        return res\n"
      ],
      "metadata": {
        "id": "pwDYDh_Ere2Q"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "# 238. Product of Array Except Self\n",
        "\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
        "        dp = [1] * len(nums)\n",
        "        dp2 = [1] * len(nums)\n",
        "        \n",
        "        for i in range(1, len(nums)):\n",
        "            dp[i] = dp[i-1] * nums[i-1] \n",
        "        \n",
        "        cur = 1\n",
        "        for i in range(len(nums)-2, -1, -1):\n",
        "            cur *= nums[i+1]\n",
        "            dp[i] *= cur\n",
        "        return dp\n",
        "\n",
        "# 152. Maximum Product Subarray\n",
        "class Solution:\n",
        "    def maxProduct(self, nums: List[int]) -> int:\n",
        "        min_cur = nums[0]\n",
        "        max_cur = nums[0]\n",
        "        \n",
        "        res = max_cur\n",
        "        \n",
        "        for n in nums[1:]:\n",
        "            cur = max(n, min_cur*n, max_cur*n)\n",
        "            min_cur = min(n, min_cur*n, max_cur*n)\n",
        "            max_cur = cur\n",
        "            res = max(res, max_cur)\n",
        "        \n",
        "        return res"
      ],
      "metadata": {
        "id": "4bOhj1izePY5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#1.\n",
        "#Prefix Sum\n",
        "#Idea: 가장 끝값(왼쪽 or 오른쪽)을 1이 선언된 result 배열(temp)에 nums[i+1]의 값을 누적 곱을 한 후,\n",
        "#      그 값을 기준으로 다시한번 반대 방향의 곳부터 temp를 선언하여 (곱이기때문에 1로 초기화) 누적 계산\n",
        "#TC : O(N), SC(1)\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
        "        result = [0] * len(nums)\n",
        "        result[len(nums)-1] = 1\n",
        "        for i in range(len(nums)-2, -1, -1):\n",
        "            result[i] = result[i+1] * nums[i+1]\n",
        "        temp = 1\n",
        "        for i in range(len(nums)):\n",
        "            result[i] = result[i] * temp\n",
        "            temp = temp*nums[i]\n",
        "        \n",
        "        return result\n",
        "#2.\n",
        "#Prefix Sum\n",
        "#Idea : 왼쪽에서 한번 subarray를 계산하면서 max값을 찾아 res에 저장\n",
        "#       오른쪽에서 다시한번 왼쪽으로 subarray 계산하면서 max 값을 찾는다.\n",
        "#       ※ 더하기가 아니라 곱하기이므로 0을만날때 다음 계산을위해 초기화 1을 해줌\n",
        "# TC : O(N), SC : O(1)\n",
        "class Solution:\n",
        "    def maxProduct(self, nums: List[int]) -> int:\n",
        "        res = -inf\n",
        "        temp = 1\n",
        "        for i in range(len(nums)):\n",
        "            \n",
        "            temp *= nums[i]\n",
        "            res = max(res,temp)\n",
        "            if temp == 0:\n",
        "                temp = 1\n",
        "        temp = 1\n",
        "        for i in range(len(nums)-1,-1,-1):\n",
        "\n",
        "            temp *= nums[i]\n",
        "            res = max(res,temp)\n",
        "            if temp == 0:\n",
        "                temp = 1 \n",
        "        return res"
      ],
      "metadata": {
        "id": "NFrOUeAshbAv"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#238\n",
        "class Solution:\n",
        "    def productExceptSelf(self, nums: List[int]) -> List[int]:\n",
        "        \n",
        "        forward = [1]*len(nums)\n",
        "        backward = [1]*len(nums)\n",
        "        res = []\n",
        "        \n",
        "        for i in range(1, len(nums)):\n",
        "            \n",
        "            forward[i] = forward[i-1]*nums[i-1]\n",
        "        \n",
        "        for i in range(len(nums)-2, -1, -1):\n",
        "            \n",
        "            backward[i] = backward[i+1]*nums[i+1]\n",
        "            \n",
        "        for i in range(len(nums)):\n",
        "            \n",
        "            res.append(forward[i]*backward[i])\n",
        "        \n",
        "        return res\n",
        "\n",
        "#152\n",
        "class Solution:\n",
        "    def maxProduct(self, nums: List[int]) -> int:\n",
        "        \n",
        "        res = max(nums)\n",
        "        cur_max, cur_min = 1, 1\n",
        "        \n",
        "        for n in nums:\n",
        "            \n",
        "            c_max = n*cur_max\n",
        "            c_min = n*cur_min\n",
        "            \n",
        "            cur_max = max(c_max, c_min, n)\n",
        "            cur_min = min(c_max, c_min, n)\n",
        "            res = max(res, cur_max)\n",
        "            \n",
        "        \n",
        "        return res"
      ],
      "metadata": {
        "id": "GM96lNCNiOJK"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 30 2022\n",
        "\n",
        "###Array\n",
        "\n",
        "https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/\n",
        "\n",
        "https://leetcode.com/problems/search-in-rotated-sorted-array/"
      ],
      "metadata": {
        "id": "60woMsTnUy4G"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def findMin(self, nums: List[int]) -> int:\n",
        "        l = 0\n",
        "        r = len(nums) - 1\n",
        "        \n",
        "        while l < r:\n",
        "            mid = (l + r) // 2\n",
        "            \n",
        "            if nums[mid] > nums[r]:\n",
        "                l = mid + 1\n",
        "            else:\n",
        "                r = mid\n",
        "        \n",
        "        return nums[l]\n",
        "\n",
        "\n",
        "# --------------------------------\n",
        "\n",
        "class Solution:\n",
        "    def search(self, nums: List[int], target: int) -> int:\n",
        "        index = 0\n",
        "        \n",
        "        if nums[0] > nums[-1]:\n",
        "            index = self.find_rotate(nums)\n",
        "        print(index, nums[index], target)\n",
        "        if nums[index] == target:\n",
        "            return index\n",
        "        if nums[index] < target <= nums[-1]:\n",
        "            return self.find_target(nums, index, len(nums)-1, target)\n",
        "        return self.find_target(nums, 0, index-1, target)\n",
        "    \n",
        "    \n",
        "    def find_rotate(self, arr):\n",
        "        low = 0\n",
        "        high = len(arr) - 1\n",
        "        \n",
        "        while low < high:\n",
        "            mid = (low+high) // 2\n",
        "            \n",
        "            if arr[mid] > arr[high]:\n",
        "                low = mid + 1\n",
        "            else:\n",
        "                high = mid\n",
        "        \n",
        "        return low\n",
        "    \n",
        "    def find_target(self, arr, low, high, target):\n",
        "        while low <= high:\n",
        "            mid = (low+high) // 2\n",
        "            \n",
        "            if arr[mid] == target:\n",
        "                return mid\n",
        "            elif arr[mid] > target:\n",
        "                high = mid - 1\n",
        "            else:\n",
        "                low = mid + 1\n",
        "        \n",
        "        return -1"
      ],
      "metadata": {
        "id": "tsLk5BQ6bHO4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#153. Find Minimum in Rotated Sorted Array\n",
        "#Banary Search\n",
        "#TC:O(log N), SC: O(1)\n",
        "class Solution:\n",
        "    def findMin(self, nums: List[int]) -> int:\n",
        "        def dfs(l, r):\n",
        "            if l == r:\n",
        "                return nums[l]\n",
        "            mid = (l + r) // 2\n",
        "            if nums[mid] < nums[r]:\n",
        "                return dfs(l, mid)\n",
        "            else:\n",
        "                return dfs(mid + 1, r)\n",
        "        \n",
        "        return dfs(0, len(nums)-1)\n",
        "\n",
        "\n",
        "'''\n",
        "33. Search in Rotated Sorted Array\n",
        "- Binary Search\n",
        "- left, right 검색시 각 조건 두개씩 체크해야한다. \n",
        "- nums[mid] 가 mid[left]보다 클땐 target이 nums[left] 와 nums[mid]사이에 있는지를 체크한다. (sorted Array)\n",
        "  있으면 right를 변경, 없으면 left를 변경 하여 범위를 좁힌다.\n",
        "  반대의 케이스도 범위를 체크하여 범위를 좁히는것이 포인트\n",
        "TC : O(log N), SC : O(1)\n",
        "'''\n",
        "class Solution:\n",
        "    def search(self, nums: List[int], target: int) -> int:\n",
        "        l, r = 0, len(nums)-1\n",
        "        while l <= r:\n",
        "            mid = (l + r) //2\n",
        "            if nums[mid] == target:\n",
        "                return mid\n",
        "            \n",
        "            if nums[l] <= nums[mid]:\n",
        "                if target >= nums[l] and target <= nums[mid]:\n",
        "                    r = mid - 1\n",
        "                else:\n",
        "                    l = mid + 1\n",
        "            else:\n",
        "                if target >= nums[mid] and target <= nums[r]:\n",
        "                    l = mid + 1\n",
        "                else:\n",
        "                    r = mid - 1\n",
        "        return -1\n"
      ],
      "metadata": {
        "id": "0IgZnCdwdUu-"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# JH\n",
        "# 153\n",
        "class Solution:\n",
        "    def findMin(self, nums: List[int]) -> int:\n",
        "        \n",
        "        res = nums[0]\n",
        "        \n",
        "        l, r = 0, len(nums) - 1\n",
        "        \n",
        "        while l <= r:\n",
        "            \n",
        "            if nums[l] < nums[r]:\n",
        "                res = min(res, nums[l])\n",
        "                break\n",
        "            \n",
        "            m = l + (r-l)//2\n",
        "            \n",
        "            res = min(res, nums[m])\n",
        "            \n",
        "            if nums[m] >= nums[l]:\n",
        "                l = m + 1\n",
        "            else:\n",
        "                r = m - 1\n",
        "        \n",
        "        return res\n",
        "\n",
        "#33\n",
        "class Solution:\n",
        "    def search(self, nums: List[int], target: int) -> int:\n",
        "        def _search(nums, target, left, right):\n",
        "            \n",
        "            if len(nums) == 1 and nums[0] != target: return -1\n",
        "            \n",
        "            mid = (left + right) // 2\n",
        "            \n",
        "            if nums[mid] == target: \n",
        "                return mid\n",
        "    \n",
        "            if nums[left] <= target < nums[mid]:\n",
        "                return _search(nums, target, left, mid-1)\n",
        "            \n",
        "            if nums[mid] < target <= nums[right]:\n",
        "                return _search(nums, target, mid+1, right)\n",
        "            \n",
        "            if nums[left] > nums[mid]:\n",
        "                return _search(nums, target, left, mid-1)\n",
        "            \n",
        "            if nums[right] < nums[mid]:\n",
        "                return _search(nums, target, mid+1, right)\n",
        "            \n",
        "            return -1\n",
        "            \n",
        "        return _search(nums,target, 0, len(nums)-1)\n",
        "        "
      ],
      "metadata": {
        "id": "L16YWiVOmssw"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#YS\n",
        "class Solution:\n",
        "    def findMin(self, nums: List[int]) -> int:\n",
        "        l = 0\n",
        "        h = len(nums)-1\n",
        "        \n",
        "        while l < h:\n",
        "            mid = (h-l) // 2 + l\n",
        "            #print(l, mid ,h)\n",
        "            if nums[mid] > nums[h]: # 3 4 5 1 2\n",
        "                l = mid + 1\n",
        "            else: #  1 2 3 4 5      \n",
        "                h = mid # - 1\n",
        "            \n",
        "        #print(l, mid ,h)\n",
        "        return nums[l]"
      ],
      "metadata": {
        "id": "UWgji18brNMv"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Mar. 31 2022\n",
        "\n",
        "https://leetcode.com/problems/merge-intervals/\n",
        "\n",
        "https://leetcode.com/problems/longest-substring-without-repeating-characters/"
      ],
      "metadata": {
        "id": "ctm2aG9J1s-U"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "        intervals.sort(key= lambda x:(x[1]))\n",
        "        #print(intervals)\n",
        "        ans = [intervals[0]]\n",
        "        for s, e in intervals:\n",
        "            if s <= ans[-1][0]: #     1  8\n",
        "                while ans and s <= ans[-1][0]:\n",
        "                    ans.pop()\n",
        "                \n",
        "            if ans and ans[-1][1] >= s: # 1 5  4 6\n",
        "                ans[-1][1] = e\n",
        "            else:\n",
        "                ans.append([s,e])\n",
        "        return ans\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
        "        seen = set()\n",
        "        deq = deque()\n",
        "        ans = 0\n",
        "        for c in s:\n",
        "            if c in seen:\n",
        "                while deq[0] != c: #  gab  g\n",
        "                    seen.remove(deq.popleft())\n",
        "                deq.popleft() # ab   g\n",
        "            else:\n",
        "                seen.add(c)\n",
        "            deq.append(c)\n",
        "            \n",
        "            ans = max(ans, len(deq))\n",
        "        \n",
        "        return max(ans, len(deq))"
      ],
      "metadata": {
        "id": "c-BILpWUq-_Q"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "        res = []\n",
        "        intervals.sort()\n",
        "        res.append(intervals[0])\n",
        "        for i in intervals[1:]:\n",
        "            if res[-1][1] < i[0]:\n",
        "                res.append(i)\n",
        "            else:\n",
        "                res[-1] = [res[-1][0], max(res[-1][1], i[1])]\n",
        "        return res\n",
        "                \n",
        "\n",
        "# -----------------------------------\n",
        "\n",
        "from collections import defaultdict\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
        "        if len(s) < 2:\n",
        "            return len(s)\n",
        "        count = defaultdict(int)\n",
        "        p1 = 0\n",
        "        res = 0\n",
        "        for i in range(len(s)):\n",
        "            while count[s[i]] > 0:\n",
        "                count[s[p1]] -= 1\n",
        "                p1 += 1\n",
        "            count[s[i]] += 1\n",
        "            res = max(res, i-p1+1)\n",
        "        return res\n",
        "        \n",
        "# -------------------------------------\n",
        "\n",
        "class Solution:\n",
        "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
        "        if len(s) < 2:\n",
        "            return len(s)\n",
        "        _map = {}\n",
        "        p1 = 0\n",
        "        res = 0\n",
        "        for i in range(len(s)):\n",
        "            if s[i] in _map:\n",
        "                p1 = max(_map[s[i]], p1)\n",
        "            res = max(res, i-p1+1)\n",
        "            _map[s[i]] = i+1\n",
        "        return res\n",
        "        "
      ],
      "metadata": {
        "id": "9iuZw84xsmBf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "# 56. Merge Intervals\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "        start, end = -1, -1\n",
        "        intervals.sort(key = lambda x:x[0])\n",
        "        res = []\n",
        "        for interval in intervals:\n",
        "            if end < interval[0]:\n",
        "                if start != -1 and end != -1:\n",
        "                    res.append([start,end])\n",
        "                start = interval[0]\n",
        "                end = interval[1]\n",
        "            else:\n",
        "                end = max(end,interval[1])\n",
        "        res.append([start,end])\n",
        "        return res\n",
        "\n",
        "\n",
        "#3. Longest Substring Without Repeating Characters\n",
        "#주호님's idea\n",
        "#two pointer left, right zero idea와 비슷하지만, 딱 s의 length 만큼 시간복잡도 사용 \n",
        "class Solution:\n",
        "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
        "        res = 0\n",
        "        map_ = dict()\n",
        "        l = 0\n",
        "        for r in range(len(s)):\n",
        "            if s[r] in map_:\n",
        "                l = max(map_[s[r]], l) #map에 들어있는 해당 문자열이랑 left랑 비교해서 left의 포지션을 right만큼 옮김\n",
        "            res = max(res, r - l + 1)\n",
        "            map_[s[r]] = r + 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "ZbW1yPAIuVd3"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "          \n",
        "        \n",
        "        intervals.sort(key=lambda x: x[0])\n",
        "        ans = []\n",
        "        i = 0\n",
        "        while i <len(intervals):\n",
        "            if i+1 < len(intervals) and intervals[i][1] >= intervals[i+1][0]: \n",
        "                t = max(intervals[i][1], intervals[i+1][1])\n",
        "                temp = [intervals[i][0], t]\n",
        "                intervals[i+1] = temp\n",
        "                i += 1\n",
        "            else:\n",
        "                ans.append(intervals[i])\n",
        "                i += 1\n",
        "                \n",
        "        return ans\n",
        "\n",
        "class Solution:\n",
        "    def lengthOfLongestSubstring(self, s: str) -> int:\n",
        "       res = 0 \n",
        "        d = {}\n",
        "        i = 0\n",
        "        for x in range(len(s)):\n",
        "            if s[x] in d:\n",
        "                i = max(d[s[x]], i)      \n",
        "            res = max(res, x - i + 1)\n",
        "            d[s[x]] = x + 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "Mt8BjSP4xcLU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#56\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\\\n",
        "        \n",
        "        intervals.sort(key=lambda x:x[0])\n",
        "        \n",
        "        stack = []\n",
        "        \n",
        "        for interval in intervals:\n",
        "            if not stack:\n",
        "                stack.append(interval)\n",
        "            else:\n",
        "                top = stack.pop()\n",
        "                if top[1] >= interval[0]:\n",
        "                    stack.append([top[0], max(top[1], interval[1])])\n",
        "                else:\n",
        "                    stack.append(top)\n",
        "                    stack.append(interval)\n",
        "        \n",
        "        return stack\n",
        "                    "
      ],
      "metadata": {
        "id": "Ptea2wGy0KMa"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        ""
      ],
      "metadata": {
        "id": "IZV-RnRv8FvD"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 1 2022\n",
        "https://leetcode.com/problems/3sum/\n",
        "\n"
      ],
      "metadata": {
        "id": "GRC-LE1c8GHA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution(object):\n",
        "    def threeSum(self, nums):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :rtype: List[List[int]]\n",
        "        \"\"\"\n",
        "        nums.sort()\n",
        "        ans = []\n",
        "        for i in range(len(nums)-2):\n",
        "            if i > 0 and nums[i-1] == nums[i]:\n",
        "                continue\n",
        "            l = i + 1\n",
        "            r = len(nums) - 1\n",
        "            while l < r:\n",
        "                s = nums[i] + nums[l] + nums[r]\n",
        "                if s == 0:\n",
        "                    ans.append([ nums[i], nums[l], nums[r] ])\n",
        "                    l += 1\n",
        "                    r -= 1\n",
        "                    \n",
        "                    while l < r and nums[r] == nums[r+1]:\n",
        "                        r -= 1\n",
        "                    while l < r and nums[l-1] == nums[l]:\n",
        "                        l += 1\n",
        "                elif s > 0:\n",
        "                    r -= 1                    \n",
        "                    \n",
        "                    while l < r and nums[r] == nums[r+1]:\n",
        "                        r -= 1\n",
        "                elif s < 0:\n",
        "                    l += 1\n",
        "                    \n",
        "                    while l < r and nums[l-1] == nums[l]:\n",
        "                        l += 1\n",
        "        return ans"
      ],
      "metadata": {
        "id": "yadichmr_rnk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit 84/318 :(\n",
        "class Solution:\n",
        "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
        "        \n",
        "        if nums == [] or len(nums) < 3:\n",
        "            return []\n",
        "        if nums == [0,0,0]: return [[0,0,0]]\n",
        "        \n",
        "        d = {}\n",
        "        seen = {}\n",
        "        for i,v in enumerate(nums):\n",
        "            d[i] = v\n",
        "        res = []\n",
        "        cur, cur_index = nums[0], 0\n",
        "        for i in range(1, len(nums)):\n",
        "            x = -cur - nums[i]\n",
        "            out = tuple(sorted((cur, nums[i], x)))\n",
        "            for j, v in d.items(): \n",
        "                if v == x and j != cur_index and j != i and i != cur_index and out not in seen:\n",
        "                    res.append(out)\n",
        "                    seen[out] = 0\n",
        "            cur, cur_index = nums[i], i\n",
        "\n",
        "        return res"
      ],
      "metadata": {
        "id": "lo_8T7WP_76I"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "TC : O(NM) n(positive) + m(negative) == nums's length \n",
        "SC: O(n)\n",
        "Idea : \n",
        "\n",
        "       음수(a+b) + 음수(c) = 음수\n",
        "       양수(a+b) + 양수(c) = 양수\n",
        "       0이 되려면 음수 + 양수 or 0 + 0 + 0\n",
        "       \n",
        "       map에 nums의 값들을 넣으면서 갯수를 세고,\n",
        "       map의 key값(중복이 제거된 num)들을 list_로 만들어서\n",
        "       0보다 작으면 negative list에 담고, \n",
        "       0보다 크면 positive list에 담는다.\n",
        "         \n",
        "       -(양수 + 음수) 양수 + 음수 의 값에 -값을 받아야 0을 만들 수 있다. 3 + (-1) = 2, -2이어야 0이니까 -2를 찾기\n",
        "       \n",
        "       map에 0이 있고 0이 세개 이상이면 그것도 답이기때문에 (0,0,0)을 넣는다\n",
        "'''\n",
        "from collections import defaultdict\n",
        "class Solution:\n",
        "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
        "        map_ = defaultdict(int)\n",
        "        pos, neg = [], []\n",
        "        res = set()\n",
        "        for num in nums:\n",
        "            map_[num] += 1\n",
        "        list_ = list(map_.keys())\n",
        "        if 0 in map_ and map_[0] >= 3:\n",
        "            res.add((0,0,0))\n",
        "        \n",
        "        for num in list_:\n",
        "            if num < 0:\n",
        "                neg.append(num)\n",
        "            elif num > 0:\n",
        "                pos.append(num)\n",
        "        for p in pos:\n",
        "            for n in neg:\n",
        "                temp = -(p + n) \n",
        "                if temp in map_:\n",
        "                    if (temp != p and temp != n) or map_[temp] > 1:\n",
        "                        res.add(tuple(sorted([p,n,temp])))\n",
        "        return res"
      ],
      "metadata": {
        "id": "jGTRuetqAA5c"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "class Solution:\n",
        "    def threeSum(self, nums: List[int]) -> List[List[int]]:\n",
        "        if len(nums) < 3:\n",
        "            return []\n",
        "        \n",
        "        nums.sort()\n",
        "        res = set()\n",
        "        for i in range(len(nums)):\n",
        "            if nums[i] > 0:\n",
        "                break\n",
        "            l = i + 1\n",
        "            r = len(nums) - 1\n",
        "            while l < r:\n",
        "                if nums[i] + nums[l] + nums[r] == 0:\n",
        "                    res.add((nums[i], nums[l], nums[r]))\n",
        "                if nums[i] + nums[l] + nums[r] > 0:\n",
        "                    r -= 1\n",
        "                else:\n",
        "                    l += 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "wTKbUVcLAL6R"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 04 2022\n",
        "https://leetcode.com/problems/container-with-most-water/\n",
        "\n",
        "https://leetcode.com/problems/sum-of-two-integers/\n",
        "\n",
        "https://leetcode.com/problems/number-of-1-bits/\n"
      ],
      "metadata": {
        "id": "TxO-6dRxIT1K"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def maxArea(self, height: List[int]) -> int:\n",
        "        i = 0\n",
        "        j = len(height) - 1\n",
        "        \n",
        "        ans = 0\n",
        "        \n",
        "        while i < j:\n",
        "            h = min(height[i], height[j])\n",
        "            w = j - i\n",
        "            \n",
        "            ans = max(ans, h*w)\n",
        "            \n",
        "            if height[i] < height[j]:\n",
        "                i += 1\n",
        "            else:\n",
        "                j -= 1\n",
        "        return ans\n",
        "\n",
        "class Solution:\n",
        "    def getSum(self, a: int, b: int) -> int:\n",
        "        return sum([a,b])\n",
        "        # 죄송\n",
        "\n",
        "class Solution:\n",
        "    def hammingWeight(self, n: int) -> int:\n",
        "        count = 0\n",
        "        num = 2 ** 31\n",
        "        while num != 1:\n",
        "            if n - num >= 0:\n",
        "                n -= num\n",
        "                count += 1\n",
        "            num = num // 2\n",
        "            #print(n, num)\n",
        "                \n",
        "        return count + n"
      ],
      "metadata": {
        "id": "tx26C_49Q-ns"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "class Solution:\n",
        "    def maxArea(self, height: List[int]) -> int:\n",
        "        p1 = 0\n",
        "        p2 = len(height) - 1\n",
        "        res = 0\n",
        "        \n",
        "        while p1 < p2:\n",
        "            res = max(res, min(height[p1], height[p2])*(p2-p1))\n",
        "            if height[p1] < height[p2]:\n",
        "                p1 += 1\n",
        "            else:\n",
        "                p2 -= 1\n",
        "        \n",
        "        return res\n",
        "\n",
        "  # ------------------------------\n",
        "\n",
        "  # ------------------------------\n",
        "  class Solution:\n",
        "    def hammingWeight(self, n: int) -> int:\n",
        "        res = 0\n",
        "        while n:\n",
        "            res += n & 1\n",
        "            n >>= 1\n",
        "        return res\n"
      ],
      "metadata": {
        "id": "CYlnSPs-YFSk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#11\n",
        "class Solution:\n",
        "    def maxArea(self, height: List[int]) -> int:\n",
        "        \n",
        "        l, r = 0, len(height)-1\n",
        "        res = 0\n",
        "        \n",
        "        while l < r:\n",
        "            width = r - l\n",
        "            height_ = min(height[l], height[r])\n",
        "            area = width * height_\n",
        "            res = max(res, area)\n",
        "            \n",
        "            if height[l] < height[r]:\n",
        "                l += 1\n",
        "            else:\n",
        "                r -= 1\n",
        "        \n",
        "        return res\n",
        "\n",
        "# 371\n",
        "?.?\n",
        "\n",
        "# 191\n",
        "class Solution:\n",
        "    def hammingWeight(self, n: int) -> int:\n",
        "        \n",
        "        return str(bin(n)).count('1')"
      ],
      "metadata": {
        "id": "kNv88uR6ZTew"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#11. Container With Most Water\n",
        "'''\n",
        "Two pointer\n",
        "left, right 크기를 비교하여 작은 값을 구하고 \n",
        "그 값이랑 distance(right - left) 곱하여 값을 구하는 방법\n",
        "\n",
        "SC : O(n), TC: O(1)\n",
        "'''\n",
        "class Solution:\n",
        "    def maxArea(self, height: List[int]) -> int:\n",
        "        l, r = 0, len(height)-1\n",
        "        res = 0\n",
        "        while l < r:\n",
        "            if height[l]<height[r]:\n",
        "                min_ = min(height[l],height[r])\n",
        "                res = max(res,min_ * (r - l))\n",
        "                l += 1\n",
        "            else:\n",
        "                min_ = min(height[l],height[r])\n",
        "                res = max(res,min_ * (r - l))\n",
        "                r -= 1\n",
        "        return res\n",
        "\n",
        "#371. Sum of Two Integers\n",
        "'''\n",
        "Full Adder\n",
        "Idea : 비트연산 중 전가산기를 사용하여 문제를 품\n",
        "       전가산기 논리식 \n",
        "         Sum : A ^ B ^ C\n",
        "         Carry : A & B | C(A ^ B)\n",
        "         \n",
        "       양수처리는 문제가 없는데 음수 처리 -16, 8 같은것들이 포인트\n",
        "       ※ 음수의 2진수는 2의보수를 취하고, 오른쪽 시프트를 할경우 가장 큰 숫자가 나온다. (-1)\n",
        "       Python은 BigInteger처럼 계속 숫자가 오르기때문에 2**31까지만 증가하면서 1로 채우고,\n",
        "       음수의 경우 2**32 - res(계산 + 왼쪽을 1로꽉채운 숫자) 하여 return\n",
        "}\n",
        "TC : O(1), SC O(1)\n",
        "'''\n",
        "class Solution:\n",
        "    def getSum(self, a: int, b: int) -> int:\n",
        "        c = 0\n",
        "        count =0 \n",
        "        res = 0\n",
        "        while (a!= 0 or b!=0  or c!= 0) and count < 32:\n",
        "            sum_ = (a & 1) ^ (b & 1) ^ c\n",
        "            c = (((a & 1) ^ (b & 1)) & c ) | ((a & 1) & (b & 1))\n",
        "            a = a >> 1\n",
        "            b = b >> 1\n",
        "            res = res | (sum_ << count)\n",
        "            count += 1\n",
        "        print(res)\n",
        "        print(2**32)\n",
        "        return res if res < 2**31 else res - 2**32\n",
        "\n",
        "#Minsu's code\n",
        "#191. Number of 1 Bits\n",
        "'''\n",
        "Bit Manipulation\n",
        "Idea:\n",
        "    오른쪽으로 한칸씩 shift하면서  1이랑 and 연산 후 값이 true면 res 증가\n",
        "    \n",
        "SC : O(1), TC: O(1)\n",
        "'''\n",
        "class Solution:\n",
        "    def hammingWeight(self, n: int) -> int:\n",
        "        res = 0\n",
        "        while n > 0:\n",
        "            if n & 1:\n",
        "                res += 1\n",
        "            n = n >> 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "sM2eUd7SaArX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 05 2022\n",
        "\n",
        "###Binary\n",
        "\n",
        "######Easy라 3개 냈습니다. 안내려다가 한번 훑는 기분으로.\n",
        "\n",
        "https://leetcode.com/problems/counting-bits/\n",
        "\n",
        "https://leetcode.com/problems/missing-number/\n",
        "\n",
        "https://leetcode.com/problems/reverse-bits/"
      ],
      "metadata": {
        "id": "aFk69fCbKYfR"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def countBits(self, n: int) -> List[int]:\n",
        "        if n == 0:\n",
        "            return [0]\n",
        "        if n == 1:\n",
        "            return [0, 1]\n",
        "        ans = [0] * (n+1)\n",
        "        ans[1] = 1\n",
        "        \n",
        "        for i in range(2, n+1):\n",
        "            ans[i] = ans[i&(i-1)] + 1\n",
        "        \n",
        "        return ans\n",
        "\n",
        "######################################\n",
        "\n",
        "  class Solution:\n",
        "    def missingNumber(self, nums: List[int]) -> int:\n",
        "        m = len(nums)\n",
        "        for i, n in enumerate(nums):\n",
        "            m ^= i ^ n\n",
        "        return m\n",
        "\n",
        "#######################################\n",
        "\n",
        "class Solution:\n",
        "    def reverseBits(self, n: int) -> int:\n",
        "        res = \"\"\n",
        "        for _ in range(32):\n",
        "            res += str(n & 1)\n",
        "            n >>= 1\n",
        "        return int(res, 2)"
      ],
      "metadata": {
        "id": "kHMMZi6NcOd1"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "#338. Counting Bits\n",
        "'''\n",
        "DP\n",
        "0은 어차피 0개\n",
        "1부터 n+1 까지 루프를 돌면서 \n",
        "i의 2진수 첫번째 자리가 1인지 체크(i & 1) 하고 배열에 넣고\n",
        "그전에 i/2의 값이 1의 개수를 체크한 것이 있으면 그 값을 가지고오고 체크한것과 더해서 누적\n",
        "ex)\n",
        "2 의 2진수 = 10 \n",
        "5 의 2진수 =  101 -> 10 1\n",
        "5 // 2 = 2\n",
        "res[2] = 1 \n",
        "5 & 1 = 1\n",
        "res[5] = res[2] + (5&1) = 2\n",
        "\n",
        "'''\n",
        "class Solution:\n",
        "    def countBits(self, n: int) -> List[int]:\n",
        "        res = [0] * (n + 1)\n",
        "        for i in range(1, n + 1):\n",
        "            res[i] = res[i // 2] + (i & 1)\n",
        "        return res\n",
        "\n",
        "\n",
        "#268. Missing Number\n",
        "'''\n",
        "Bitmask\n",
        "mask에 length + 1 지수만큼 제곱 -1값을 넣어주고\n",
        "nums[i]의 자리만큼 mask에서 뺀다.\n",
        "length만큼 돌아서 2^i값이 계산된 mask값이랑 같으면 result에 i를 넣어주고 break\n",
        "모두 돌아도 break값만큼 나오지 않으면 마지막 값이 result\n",
        "'''\n",
        "class Solution:\n",
        "    def missingNumber(self, nums: List[int]) -> int:\n",
        "        length = len(nums)\n",
        "        mask = 2**(length+1) -1\n",
        "        for i in range(length):\n",
        "            temp = 1 << nums[i]\n",
        "            mask -=temp\n",
        "        res = -1\n",
        "        for i in range(length):\n",
        "            if mask == pow(2,i):\n",
        "                res = i\n",
        "                break\n",
        "        return res if res != -1 else length\n",
        "\n",
        "\n",
        "#190. Reverse Bits\n",
        "class Solution:\n",
        "    def reverseBits(self, n: int) -> int:\n",
        "        res = 0\n",
        "        for i in range(32):\n",
        "            temp = n & 1\n",
        "            res = res << 1\n",
        "            res = res | temp\n",
        "            n  = n >> 1\n",
        "        return res"
      ],
      "metadata": {
        "id": "u8t7LBY2iWxu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH \n",
        "\n",
        "#338\n",
        "class Solution:\n",
        "    def countBits(self, n: int) -> List[int]:      \n",
        "        res = [0] * (n + 1)\n",
        "\n",
        "        for i in range(1, n+1):\n",
        "            res[i] = res[i//2] + i%2 \n",
        "            \n",
        "        return res\n",
        "\n",
        "#268\n",
        "class Solution:\n",
        "    def missingNumber(self, nums: List[int]) -> int:      \n",
        "        l = len(nums)\n",
        "        nums = set(nums)\n",
        "        \n",
        "        for i in range(l+1):\n",
        "            if i not in nums:\n",
        "                return i\n",
        "        \n",
        "#190\n",
        "class Solution:\n",
        "    def reverseBits(self, n: int) -> int:\n",
        "        number = str(bin(n)[2::][::-1])\n",
        "        \n",
        "        while len(number) < 32:\n",
        "            number += '0'\n",
        "            \n",
        "        return int(number, 2)\n",
        "        \n"
      ],
      "metadata": {
        "id": "CvU6KyGEkac9"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def countBits(self, n: int) -> List[int]:\n",
        "        ans = [0]\n",
        "        power_two = 2\n",
        "        for i in range(1,n+1):\n",
        "            if i % 2 == 1: # odd\n",
        "                ans.append(ans[-1] + 1)\n",
        "            else:\n",
        "                if i == power_two:\n",
        "                    ans.append(1)\n",
        "                    power_two = power_two << 1\n",
        "                    #print(i, power_two)\n",
        "                else:\n",
        "                    #print(i, power_two)\n",
        "                    ans.append(ans[-(power_two >> 1) + 1])\n",
        "        return ans\n",
        "\n",
        "class Solution:\n",
        "    def missingNumber(self, nums: List[int]) -> int:\n",
        "        total = 0\n",
        "        for i in range(len(nums)+1):\n",
        "            total += i\n",
        "        for i in nums:\n",
        "            total -= i\n",
        "        return total"
      ],
      "metadata": {
        "id": "wcKNbrOamQQO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 06 2022\n",
        "\n",
        "###DP\n",
        "\n",
        "https://leetcode.com/problems/climbing-stairs/\n",
        "\n",
        "https://leetcode.com/problems/coin-change/"
      ],
      "metadata": {
        "id": "G6nQJVueq5Ie"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "'''\n",
        "fibonacci\n",
        "dp배울때 푸는 대표 문제\n",
        "\n",
        "TC : O(n)\n",
        "'''\n",
        "class Solution:\n",
        "    def climbStairs(self, n: int) -> int:\n",
        "        dp = [0] * (n+1)\n",
        "        dp[0] = 1\n",
        "        dp[1] = 1\n",
        "        for i in range(2,n+1):\n",
        "            dp[i] = dp[i - 1] + dp[i - 2]\n",
        "        return dp[n]\n",
        "'''\n",
        "DP\n",
        "coin의 값이 해당 money보다 작을때 Money - Coins 의 Value를 가지고와서 해당 coin의 1개를 추가했을때의 값과 비교하여 작은값을 누적\n",
        "\n",
        "Money: 1,2,3,4,5,6,7,8,9,10,11\n",
        "Coins\n",
        "    1:0,1,2,3,4,5,6,7,8,9,10,11\n",
        "    2:  1,1,2,2,3,3,4,4,5,5,6\n",
        "    5:  1,1,2,2,1,2,2,3,3,2,3\n",
        "\n",
        "TC: O(nm) : n : Length of Coins , m : amount\n",
        "'''\n",
        "class Solution:\n",
        "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
        "        dp = [inf] * (amount + 1)\n",
        "        dp[0] = 0\n",
        "        \n",
        "        for i in range(1, amount+1):\n",
        "            for j in range(len(coins)):\n",
        "                if coins[j] <= i:\n",
        "                    dp[i] = min(dp[i], dp[i - coins[j]] + 1)\n",
        "                \n",
        "        return dp[amount] if dp[amount]!=inf else -1"
      ],
      "metadata": {
        "id": "xK1-LlysR9uA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def climbStairs(self, n: int) -> int:\n",
        "        if n < 2:\n",
        "            return n\n",
        "        dp = [1, 2]\n",
        "        res = 2\n",
        "        for _ in range(2, n):\n",
        "            res = sum(dp)\n",
        "            dp[0], dp[1] = dp[1], res\n",
        "        return res\n",
        "\n",
        "########################################\n",
        "\n",
        "class Solution:\n",
        "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
        "        dp = [float('inf')] * (amount+1)\n",
        "        dp[0] = 0\n",
        "        \n",
        "        for coin in coins:\n",
        "            for i in range(coin, amount+1):\n",
        "                dp[i] = min(dp[i], dp[i-coin] + 1)\n",
        "        \n",
        "        return dp[-1] if dp[-1] != float('inf') else -1"
      ],
      "metadata": {
        "id": "gN7p7TBWs4Fq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#70\n",
        "class Solution:\n",
        "    def climbStairs(self, n: int) -> int:\n",
        "        \n",
        "        if n < 4:\n",
        "            return n\n",
        "        \n",
        "        prev1 = 1 \n",
        "        prev2 = 2\n",
        "        \n",
        "        for i in range(3, n+1):\n",
        "            curr = prev1 + prev2\n",
        "            prev1 = prev2\n",
        "            prev2 = curr\n",
        "        \n",
        "        return prev2\n",
        "\n",
        "\n",
        "#322\n",
        "class Solution:\n",
        "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
        "        \n",
        "        dp = [float('inf')]*(amount+1)\n",
        "        \n",
        "        dp[0] = 0\n",
        "        \n",
        "        for coin in coins:\n",
        "            for i in range(coin, amount+1):\n",
        "                dp[i] = min(dp[i], dp[i-coin]+1)\n",
        "        \n",
        "        return dp[-1] if dp[-1] != float('inf') else -1"
      ],
      "metadata": {
        "id": "mq_g0gVxuJ2B"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit \n",
        "# at 1 -> 1 (1)\n",
        "        # 2 -> 1,1 or 2 (2)\n",
        "        # 3 -> 1,1,1 or 2,1 or 1,2 (3)\n",
        "        # 4 -> 1,1,1,1 or 1,1,2, 2,1,1, 2,2, 1,2,1 (5)\n",
        "        \n",
        "        \n",
        "        if n == 0: return 0  # edge case\n",
        "        \n",
        "        if n == 1 or n == 2:\n",
        "            return n\n",
        "        \n",
        "        record = [0] * (n + 1)\n",
        "        record[1] = 1\n",
        "        record[2] = 2\n",
        "    \n",
        "        for i in range(3, n + 1):\n",
        "            current_calculation = record[i-1] + record[i-2]\n",
        "            record[i] = current_calculation\n",
        "        \n",
        "        return record[n]\n",
        "        \n",
        "class Solution:\n",
        "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
        "        \n",
        "        dp = [float('inf') for i in range(amount + 1)]\n",
        "        dp[0] = 0\n",
        "        \n",
        "        for coin in coins:\n",
        "            for x in range(coin, amount + 1):\n",
        "                dp[x] = min(dp[x], dp[x - coin] + 1)\n",
        "        return dp[amount] if dp[amount] != float('inf') else - 1"
      ],
      "metadata": {
        "id": "qeSM8Ybbvg8f"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def climbStairs(self, n: int) -> int:\n",
        "        dic = {}\n",
        "        def help(num):\n",
        "            if num in dic:\n",
        "                return dic[num]\n",
        "            if num == 0:\n",
        "                return 1\n",
        "            elif num < 0:\n",
        "                return 0\n",
        "            \n",
        "            dic[num] = help(num-1) + help(num-2)\n",
        "            return dic[num]\n",
        "            \n",
        "        help(n)\n",
        "        \n",
        "        return dic[n]\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def coinChange(self, coins: List[int], amount: int) -> int:\n",
        "        dp = [math.inf] * (amount+1)\n",
        "        dp[0] = 0\n",
        "        for i in range(len(dp)):\n",
        "            for c in coins:\n",
        "                if i-c >= 0:\n",
        "                    dp[i] = min(dp[i], dp[i-c] + 1)\n",
        "        \n",
        "        return dp[amount] if dp[amount] != math.inf else -1"
      ],
      "metadata": {
        "id": "Alr1QZiBwdoN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 07 2022\n",
        "\n",
        "###DP\n",
        "\n",
        "https://leetcode.com/problems/longest-increasing-subsequence/\n",
        "\n",
        "https://leetcode.com/problems/word-break/"
      ],
      "metadata": {
        "id": "pAUpI_k51uCd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "class Solution:\n",
        "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
        "        \n",
        "        words = set(wordDict)\n",
        "        q = collections.deque([0])\n",
        "        seen = set()\n",
        "\n",
        "        while q:\n",
        "            i = q.popleft()\n",
        "            if i in seen:\n",
        "                continue\n",
        "            \n",
        "            for j in range(i+1, len(s)+1):\n",
        "                if s[i:j] in words:\n",
        "                    q.append(j)\n",
        "                    if j == len(s): return True\n",
        "            \n",
        "            seen.add(i)\n",
        "        \n",
        "        return False\n",
        "\n",
        "  class Solution:\n",
        "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
        "        \n",
        "        res = []\n",
        "        \n",
        "        for n in nums:\n",
        "            \n",
        "            if not res or res[-1] < n:\n",
        "                res.append(n)\n",
        "                \n",
        "            else:\n",
        "                i = bisect_left(res, n)\n",
        "                res[i] = n\n",
        "        \n",
        "        return len(res)\n",
        "                \n",
        "                "
      ],
      "metadata": {
        "id": "ph3YQuEs0kMu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
        "        res = 1\n",
        "        dp = [1] * len(nums)\n",
        "        \n",
        "        for i in range(1, len(nums)):\n",
        "            for j in range(i):\n",
        "                if nums[i] > nums[j]:\n",
        "                    dp[i] = max(dp[i], dp[j]+1)\n",
        "                    res = max(res, dp[i]) \n",
        "        return res\n",
        "\n",
        "#####################################################\n",
        "\n",
        "class Solution:\n",
        "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
        "        words = set(wordDict)\n",
        "        dp = [False] * (len(s) + 1)\n",
        "        dp[0] = True\n",
        "        for i in range(1, len(s)+1):\n",
        "            for j in range(i):\n",
        "                if dp[j] and s[j:i] in words:\n",
        "                    dp[i] = True\n",
        "        return dp[len(s)]"
      ],
      "metadata": {
        "id": "8EJ_bVyy1BZK"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "class Solution:\n",
        "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
        "        \n",
        "        N = len(nums)\n",
        "        dp = [1] * N\n",
        "        \n",
        "        for i in range(1, N):\n",
        "            for j in range(i):\n",
        "                if nums[i] > nums[j]:\n",
        "                    dp[i] = max(dp[j]+1, dp[i])\n",
        "                    \n",
        "        return max(dp)\n",
        "        \n",
        "class Solution:\n",
        "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
        "        \n",
        "        word_set = set(wordDict)\n",
        "        q = deque()\n",
        "        q.append(0)\n",
        "        seen = set()\n",
        "        while q:\n",
        "            i = q.popleft()\n",
        "            if i in seen:\n",
        "                continue\n",
        "            for j in range (i+1, len(s)+1):\n",
        "                if s[i:j] in word_set:\n",
        "                    q.append(j)\n",
        "                    if j == len(s):\n",
        "                        return True\n",
        "            seen.add(i)\n",
        "        return False"
      ],
      "metadata": {
        "id": "2fClHuBw3DtO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "DP\n",
        "nums[i] < nums[i+1] 로 count를 누적을 했을때는\n",
        "[4,10,4,3,8,9] 이 케이스 (중간에 큰수가 생겼을때)\n",
        "WA가 나옴.\n",
        "누적을 i까지의 작은수 중 max값을 찾아 +1을 해 답을 구하는 점화식\n",
        "조건 1 : nums[i] > nums[j] \n",
        "조건 2 : dp[j]중 max_값을 dp[i]에 +1하여 넣어준다.\n",
        "\n",
        "TC : O(n^2)\n",
        "'''\n",
        "class Solution:\n",
        "    def lengthOfLIS(self, nums: List[int]) -> int:\n",
        "        dp = [0] * len(nums)\n",
        "        res = 0\n",
        "        for i in range(len(nums)):\n",
        "            max_ = 0\n",
        "            for j in range(i):\n",
        "                if nums[i] > nums[j] and dp[j] > max_:\n",
        "                    max_ = dp[j]\n",
        "            \n",
        "            dp[i] = max_ + 1\n",
        "            if res < dp[i]:\n",
        "                res = dp[i]\n",
        "        return res\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n",
        "        set_ = set(wordDict)\n",
        "        dp = [False] * (len(s) + 1)\n",
        "        \n",
        "        dp[0] = True\n",
        "        for i in range(1, len(s)+1):\n",
        "            for j in range(i+1):\n",
        "                if s[j:i] in set_:\n",
        "                    if dp[j]:\n",
        "                        dp[i] = True\n",
        "                        break\n",
        "        return dp[len(s)]"
      ],
      "metadata": {
        "id": "hyA69Kq84Imt"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 08 2022\n",
        "dp\n",
        "https://leetcode.com/problems/combination-sum-iv/\n",
        "\n",
        "https://leetcode.com/problems/house-robber/\n"
      ],
      "metadata": {
        "id": "cTnFRWUl9QC7"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Joe\n",
        "\n",
        "class Solution:\n",
        "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
        "        dp = [0] * (target+1)\n",
        "        dp[0] = 1\n",
        "        \n",
        "        for t in range(target+1):\n",
        "            for n in nums:\n",
        "                if t - n >= 0:\n",
        "                    dp[t] += dp[t-n]\n",
        "                else:\n",
        "                    break\n",
        "        return dp[target]\n",
        "\n",
        "#####################################\n",
        "\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        if len(nums) <= 2:\n",
        "            return max(nums)\n",
        "        \n",
        "        dp = [0] * len(nums)\n",
        "        \n",
        "        \n",
        "        dp[0] = nums[0]\n",
        "        dp[1] = max(nums[:2])\n",
        "        \n",
        "        for i in range(2, len(nums)):\n",
        "            dp[i] = max(dp[i-2]+nums[i], dp[i-1])\n",
        "            \n",
        "        return dp[-1]"
      ],
      "metadata": {
        "id": "2I_HDFKB8Qmi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Hanbit\n",
        "\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "                \n",
        "        if len(nums) < 3:\n",
        "            return max(nums)\n",
        "        \n",
        "        dp = [0] * len(nums)\n",
        "        \n",
        "        dp[0] = nums[0]\n",
        "        dp[1] = max(nums[0], nums[1])\n",
        "        \n",
        "        for i in range(2, len(nums)):\n",
        "            dp[i] = max(nums[i]+dp[i-2], dp[i-1])\n",
        "        \n",
        "        return dp[-1]\n",
        "        \n",
        "class Solution:\n",
        "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
        "        \n",
        "        dp = [0] * (target+1)\n",
        "        \n",
        "        dp[0] = 1\n",
        "        \n",
        "        for i in range(1, target+1):\n",
        "            for j in nums:\n",
        "                if i - j >= 0:\n",
        "                    dp[i] += dp[i-j]\n",
        "            \n",
        "        return dp[-1]"
      ],
      "metadata": {
        "id": "xcEyda5J-Hg3"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#377\n",
        "class Solution:\n",
        "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
        "        \n",
        "        dp = [0]*(target+1)\n",
        "        \n",
        "        dp[0] = 1\n",
        "        \n",
        "        for i in range(1, target+1):\n",
        "            for n in nums:\n",
        "                if i - n >= 0:\n",
        "                    dp[i] += dp[i-n]\n",
        "            \n",
        "        return dp[-1]\n",
        "\n",
        "#198\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        \n",
        "        if len(nums) == 1:\n",
        "            return nums[0]\n",
        "        \n",
        "        dp = [0]*len(nums)\n",
        "        dp[0] = nums[0]\n",
        "        dp[1] = max(nums[0], nums[1])\n",
        "        \n",
        "        for i in range(2, len(nums)):\n",
        "            dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
        "        \n",
        "        return dp[-1]"
      ],
      "metadata": {
        "id": "OG2XtHK0BgGa"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "\n",
        "class Solution:\n",
        "    def combinationSum4(self, nums: List[int], target: int) -> int:\n",
        "        dic = {}\n",
        "        \n",
        "        def func(t):\n",
        "            if t in dic:\n",
        "                return dic[t]\n",
        "            if t == 0:\n",
        "                return 1\n",
        "            if t < 0:\n",
        "                return 0\n",
        "            \n",
        "            res = 0\n",
        "            for n in nums:\n",
        "                dic[t-n] = func(t-n)\n",
        "                res += dic[t-n]\n",
        "            \n",
        "            return res\n",
        "        \n",
        "        res = 0\n",
        "        for n in nums:\n",
        "            res += func(target - n)\n",
        "        \n",
        "        return res\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        if len(nums) < 3:\n",
        "            return max(nums)\n",
        "        dp = [0] * len(nums)\n",
        "        dp[0] = nums[0]\n",
        "        dp[1] = max(nums[0],nums[1])\n",
        "        for i in range(2,len(dp)):\n",
        "            dp[i] = max(dp[i-1], dp[i-2] + nums[i])\n",
        "        \n",
        "        return dp[-1]"
      ],
      "metadata": {
        "id": "xDdKWwe6DOGA"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 11 2022\n",
        "####dp\n",
        "https://leetcode.com/problems/house-robber-ii/\n",
        "\n",
        "https://leetcode.com/problems/decode-ways/\n"
      ],
      "metadata": {
        "id": "-s-n1HRtcSO8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "시작부터 마지막 미포함, 시작+1부터 마지막까지 두개로 조건 누적을 해서 \n",
        "두개를 비교해서 max값 리턴 \n",
        "조건 : 한개 건너 합을 할 수 있음. 시작 과 마지막은 \n",
        "'''\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        if len(nums)==1:\n",
        "            return nums[0]\n",
        "        start = [0] * len(nums)\n",
        "        last = [0] * len(nums)\n",
        "        start[0], start[1] = nums[0], max(nums[0],nums[1])\n",
        "        last[0], last[1] = 0, nums[1]\n",
        "        \n",
        "        for i in range(2, len(nums)):\n",
        "            start[i] = max(start[i-1],nums[i] + start[i-2])\n",
        "            last[i] = max(last[i-1],nums[i] + last[i-2])\n",
        "        \n",
        "        return max(start[len(nums)-2],last[len(nums)-1])\n",
        "\n",
        "'''\n",
        "뒤에서 부터 돌면서 0~9이면 1개\n",
        "2자리 숫자가 27밑이면 (2자리 이상일때마다 누적된 갯수 더함 1 2 3 5)\n",
        "'''\n",
        "class Solution:\n",
        "    def numDecodings(self, s: str) -> int:\n",
        "        dp = [0] * (len(s) + 1)\n",
        "        dp[len(s)] = 1\n",
        "        if 0 < int(s[-1]) < 10:\n",
        "            dp[len(s)-1] = 1\n",
        "        for i in range(len(s)-2,-1,-1):\n",
        "            if 0 < int(s[i]) < 10:\n",
        "                dp[i] = dp[i+1]\n",
        "                if 9 < int(s[i:i+2]) < 27:\n",
        "                    dp[i] = dp[i+1] + dp[i+2]\n",
        "        return dp[0] "
      ],
      "metadata": {
        "id": "mvoeHvCsUHTx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        if len(nums) < 3:\n",
        "            return max(nums)\n",
        "        \n",
        "        dp = [0] * len(nums)\n",
        "        dp[0] = nums[0]\n",
        "        \n",
        "        for i in range(1,len(nums)-1):\n",
        "            dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
        "        \n",
        "        ans = dp[-2]\n",
        "        \n",
        "        dp = [0] * len(nums)\n",
        "        dp[1] = nums[1]\n",
        "        for i in range(2,len(nums)):\n",
        "            dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
        "        \n",
        "        \n",
        "        return max(ans,dp[-1])\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def numDecodings(self, s: str) -> int:\n",
        "        dic = {}\n",
        "        def help(i):\n",
        "            if i in dic:\n",
        "                return dic[i]\n",
        "            if i == len(s):\n",
        "                return 1\n",
        "            \n",
        "            if i > len(s):\n",
        "                return 0\n",
        "            \n",
        "            res = 0\n",
        "            if i < len(s)-1 and s[i] != '0' and 10 <= int(s[i:i+2]) <= 26:\n",
        "                res += help(i+2)\n",
        "            if s[i] != '0':\n",
        "                res += help(i+1)\n",
        "            \n",
        "            dic[i] = res\n",
        "            return res\n",
        "        \n",
        "        return help(0)"
      ],
      "metadata": {
        "id": "6f14DzhdabYG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#213\n",
        "class Solution:\n",
        "    def rob(self, nums: List[int]) -> int:\n",
        "        \n",
        "        l = len(nums)\n",
        "        \n",
        "        if l < 4:\n",
        "            return max(nums)\n",
        "        \n",
        "        def get_max(nums):\n",
        "            dp = [0]*len(nums)\n",
        "            dp[0] = nums[0]\n",
        "            dp[1] = max(nums[0], nums[1])\n",
        "\n",
        "            for i in range(2, len(nums)):\n",
        "                dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
        "            \n",
        "            return dp[-1]\n",
        "        \n",
        "        \n",
        "        return max(get_max(nums[:-1]), get_max(nums[1:]))\n",
        "    \n",
        "\n",
        "#91 \n",
        "class Solution:\n",
        "    def numDecodings(self, s: str) -> int:\n",
        "        \n",
        "        \n",
        "        dp = [0]*(len(s)+1)\n",
        "        dp[len(s)] = 1\n",
        "        \n",
        "        for i in range(len(s)-1, -1 ,-1):\n",
        "            # if s[i] == '0':\n",
        "            #     dp[i] = 0\n",
        "            if s[i] != '0':\n",
        "              dp[i] = dp[i+1]\n",
        "    \n",
        "            if (i+1 < len(s) and (s[i] == '1' or s[i] == '2' and s[i+1] in '0123456')):\n",
        "                dp[i] += dp[i+2]\n",
        "    \n",
        "        return dp[0]\n"
      ],
      "metadata": {
        "id": "Xmyj7byVdH4s"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 12 2022\n",
        "####dp\n",
        "https://leetcode.com/problems/unique-paths/\n",
        "\n",
        "https://leetcode.com/problems/jump-game/\n"
      ],
      "metadata": {
        "id": "3-LpgWqxDS6r"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def uniquePaths(self, m: int, n: int) -> int:\n",
        "        dp = [[0] * n for _ in range(m)]\n",
        "        for i in range(m):\n",
        "            dp[i][0] = 1\n",
        "        for i in range(n):\n",
        "            dp[0][i] = 1\n",
        "        \n",
        "        for i in range(1, m):\n",
        "            for j in range(1, n):\n",
        "                dp[i][j] = dp[i-1][j] + dp[i][j-1]\n",
        "        \n",
        "        return dp[m-1][n-1]\n",
        "'''\n",
        "'''\n"
      ],
      "metadata": {
        "id": "WVSa8HcrjiOi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#Unique Paths\n",
        "class Solution:\n",
        "    def uniquePaths(self, m: int, n: int) -> int:\n",
        "        \n",
        "        row = [1] * n\n",
        "        \n",
        "        for i in range(m-1):\n",
        "            temp = [1] * n\n",
        "            for j in range(n-2, -1, -1):\n",
        "                temp[j] = temp[j + 1] + row[j]\n",
        "            row = temp\n",
        "        \n",
        "        return row[0]\n",
        "\n",
        "#Jump Game\n",
        "class Solution:\n",
        "    def canJump(self, nums: List[int]) -> bool:\n",
        "        \n",
        "        goal = len(nums) - 1\n",
        "        \n",
        "        for i in range(len(nums)-2, -1, -1):\n",
        "\n",
        "            if i + nums[i] >= goal:\n",
        "                goal = i\n",
        "      \n",
        "        return True if goal == 0 else False"
      ],
      "metadata": {
        "id": "HJcJ8xzenqzR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "\n",
        "class Solution:\n",
        "    def uniquePaths(self, m: int, n: int) -> int:\n",
        "        total = (m - 1) + (n - 1)\n",
        "        if total == 0:\n",
        "            return 1\n",
        "        small = min(m-1,n-1)\n",
        "        \n",
        "        ans = 1\n",
        "        for i in range(1,small+1):\n",
        "            ans = ans * total\n",
        "            ans = ans // i\n",
        "            \n",
        "            total -= 1\n",
        "        \n",
        "        return ans\n",
        "\n",
        "class Solution:\n",
        "    def canJump(self, nums: List[int]) -> bool:\n",
        "        arr = [False] * len(nums)\n",
        "        \n",
        "        arr[-1] = True\n",
        "        \n",
        "        for i in range(len(nums)-2, -1, -1):\n",
        "            for j in range( min(i+nums[i], len(nums)-1), i, -1 ) :\n",
        "                if arr[j]:\n",
        "                    arr[i] = True\n",
        "                    break\n",
        "           #print(arr)\n",
        "        return arr[0]"
      ],
      "metadata": {
        "id": "lWdApg1_pmQU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "lZw6nIaPsl2t"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Apr. 13 2022\n",
        "graph\n",
        "https://leetcode.com/problems/clone-graph/\n",
        "\n",
        "\n",
        "https://leetcode.com/problems/course-schedule/"
      ],
      "metadata": {
        "id": "JIZCXgRysmri"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "WA\n",
        "'''\n",
        "from collections import deque\n",
        "class Solution:\n",
        "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
        "        que = deque()\n",
        "        que.append(node)\n",
        "        res = dict()\n",
        "        res[node.val] = Node(node.val, [])\n",
        "        while que:\n",
        "            temp = que.popleft()\n",
        "            print(temp.neighbors)\n",
        "            for nei in temp.neighbors:\n",
        "                if nei.val not in res:\n",
        "                    res[nei.val] = Node(nei.val, [])\n",
        "                    que.append(nei)\n",
        "                res[temp.val].neighbors.append(Node(nei.val,[]))\n",
        "        \n",
        "        return res[node.val]\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
        "        def checkCycle(curr, graph, visited):\n",
        "            if visited[curr]==1:\n",
        "                return True\n",
        "            if visited[curr]== 2 or curr not in graph:\n",
        "                return False\n",
        "            visited[curr] = 1\n",
        "            for course in graph[curr]:\n",
        "                if checkCycle(course, graph, visited):\n",
        "                    return True\n",
        "            \n",
        "            visited[curr] = 2\n",
        "            return False\n",
        "        \n",
        "        \n",
        "        graph = defaultdict(list)\n",
        "        for pre in prerequisites:\n",
        "            graph[pre[1]].append(pre[0])\n",
        "            \n",
        "        visited = [0] * numCourses\n",
        "        for i in range(numCourses):\n",
        "            if checkCycle(i, graph, visited):\n",
        "                return False\n",
        "        return True"
      ],
      "metadata": {
        "id": "NdsTG6mKg6Pn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
        "        if not node:\n",
        "            return node\n",
        "        dic = {}\n",
        "        def help(node):\n",
        "            if node in dic:\n",
        "                return dic[node]\n",
        "            \n",
        "            new_node = Node(node.val, None)\n",
        "            dic[node] = new_node\n",
        "            \n",
        "            for n in node.neighbors:\n",
        "                new_n = help(n)\n",
        "                new_node.neighbors.append(new_n)\n",
        "            \n",
        "            return new_node\n",
        "        \n",
        "        return help(node)\n",
        "\n",
        "class Solution:\n",
        "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
        "        next_course = collections.defaultdict(list)\n",
        "        number_of_pre = [0] * numCourses\n",
        "        \n",
        "        for course, pre in prerequisites:\n",
        "            next_course[pre].append(course)\n",
        "            number_of_pre[course] += 1\n",
        "        \n",
        "        deq = deque()\n",
        "        \n",
        "        for c,n in enumerate(number_of_pre):\n",
        "            if n == 0:\n",
        "                deq.append(c)\n",
        "                \n",
        "        cnt = 0\n",
        "        while deq:\n",
        "            c = deq.popleft()\n",
        "            cnt += 1\n",
        "            \n",
        "            for next_c in next_course[c]:\n",
        "                number_of_pre[next_c] -= 1\n",
        "                if number_of_pre[next_c] == 0:\n",
        "                    deq.append(next_c)\n",
        "        \n",
        "        return cnt == numCourses"
      ],
      "metadata": {
        "id": "pmxlGW9dw3tP"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "class Solution:\n",
        "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
        "        if not node:\n",
        "            return node\n",
        "        clone = {}\n",
        "        \n",
        "        q = collections.deque([node])\n",
        "        \n",
        "        clone[node] = Node(node.val)\n",
        "        \n",
        "        while q:\n",
        "            curr_n = q.popleft()\n",
        "\n",
        "            for n in curr_n.neighbors:\n",
        "                if n not in clone:\n",
        "                    clone[n] = Node(n.val)\n",
        "                    q.append(n)\n",
        "\n",
        "                clone[curr_n].neighbors.append(clone[n])       \n",
        "\n",
        "        return clone[node]\n",
        "\n",
        "class Solution:\n",
        "    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:\n",
        "\n",
        "        map_ = defaultdict(list)\n",
        "        \n",
        "        for course, pre in prerequisites:\n",
        "            map_[course].append(pre)\n",
        "\n",
        "        visited = set()\n",
        "        def dfs(course):\n",
        "            if course in visited:\n",
        "                return False\n",
        "            if not map_[course]:\n",
        "                return True\n",
        "            \n",
        "            visited.add(course)    \n",
        "            for _ in range(len(map_[course])):\n",
        "                pre = map_[course].pop()\n",
        "                if not dfs(pre): return False\n",
        "            visited.remove(course)\n",
        "            return True\n",
        "        \n",
        "        for i in range(numCourses):\n",
        "            if not dfs(i): return False\n",
        "        return True\n",
        "        "
      ],
      "metadata": {
        "id": "wzmKEpZHxVxW"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "h5R-r1rtGXE7"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Apr. 14 2022\n",
        "\n",
        "###Graph\n",
        "\n",
        "https://leetcode.com/problems/pacific-atlantic-water-flow/\n",
        "\n",
        "https://leetcode.com/problems/number-of-islands/"
      ],
      "metadata": {
        "id": "kuSAKlISGX7Z"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "class Solution:\n",
        "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
        "        rows = len(heights)\n",
        "        cols = len(heights[0])\n",
        "        pacific = [[False] * cols for _ in range(rows)]\n",
        "        atlantic = [[False] * cols for _ in range(rows)]\n",
        "        \n",
        "        def dfs(row, col, check):\n",
        "            dirs = ((1,0),(-1,0),(0,1),(0,-1))\n",
        "            check[row][col] = True\n",
        "            for d in dirs:\n",
        "                dy = d[0] + row\n",
        "                dx = d[1] + col\n",
        "                if(dy < rows and dy >= 0 and dx < cols and dx >= 0 and heights[row][col] <= heights[dy][dx] and check[dy][dx]==False):\n",
        "                    dfs(dy, dx, check)\n",
        "                    \n",
        "        for i in range(rows):\n",
        "            dfs(i, 0, pacific)\n",
        "            dfs(i, cols-1, atlantic)\n",
        "        \n",
        "        for i in range(cols):\n",
        "            dfs(0, i, pacific)\n",
        "            dfs(rows-1, i, atlantic)\n",
        "        \n",
        "        res = list()\n",
        "        for i in range(rows):\n",
        "            for j in range(cols):\n",
        "                if pacific[i][j] and atlantic[i][j]:\n",
        "                    res.append([i,j])\n",
        "                    \n",
        "        return res\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def numIslands(self, grid: List[List[str]]) -> int:\n",
        "        cnt = 0\n",
        "        rows = len(grid)\n",
        "        cols = len(grid[0])\n",
        "        g = [[0] * (cols+1) for _ in range(rows+1)]\n",
        "        \n",
        "        def dfs(x, y, cnt):\n",
        "            g[x][y]=cnt\n",
        "            dirs = ((1,0),(-1,0),(0,1),(0,-1))\n",
        "            for d in dirs:\n",
        "                dx = d[0] + x\n",
        "                dy = d[1] + y\n",
        "                if dx < rows and dx >=0 and dy < cols and dy >= 0 and grid[dx][dy]==\"1\" and g[dx][dy]==0:\n",
        "                    dfs(dx, dy, cnt)\n",
        "        \n",
        "        for i in range(rows):\n",
        "            for j in range(cols):\n",
        "                if grid[i][j]==\"1\" and g[i][j]==0:\n",
        "                    cnt += 1\n",
        "                    dfs(i, j, cnt)\n",
        "        \n",
        "        return cnt"
      ],
      "metadata": {
        "id": "H6ICP1DFjJfk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#Pacific Atlantic Water flow\n",
        "class Solution:\n",
        "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
        "        \n",
        "        m = len(heights)\n",
        "        n = len(heights[0])\n",
        "        \n",
        "        pacific = set()\n",
        "        atlantic = set()\n",
        "        \n",
        "        def dfs(r,c, visited_set):\n",
        "            visited_set.add((r,c))\n",
        "            \n",
        "            for n_r, n_c in [(r+1,c), (r-1, c), (r, c+1), (r, c-1)]:\n",
        "                if 0 <= n_r < m and 0 <= n_c < n and (n_r,n_c) not in visited_set and heights[n_r][n_c] >= heights[r][c]:\n",
        "                    dfs(n_r, n_c, visited_set)\n",
        "        \n",
        "        \n",
        "        for r in range(m):\n",
        "            dfs(r, 0, pacific)\n",
        "            dfs(r, n-1, atlantic)\n",
        "        \n",
        "        for c in range(n):\n",
        "            dfs(0, c, pacific)\n",
        "            dfs(m-1, c, atlantic)\n",
        "\n",
        "        return list(pacific.intersection(atlantic))\n",
        "\n",
        "# Number of Islands\n",
        "class Solution:\n",
        "    def numIslands(self, grid: List[List[str]]) -> int:\n",
        "        \n",
        "        def dfs(m, n, grid):\n",
        "            if  0 > m or 0 > n or m >= len(grid) or n >= len(grid[0]) or grid[m][n] != '1':\n",
        "                return\n",
        "            \n",
        "            grid[m][n] = '0'\n",
        "            dfs(m+1, n, grid)\n",
        "            dfs(m-1, n, grid)\n",
        "            dfs(m, n+1, grid)\n",
        "            dfs(m, n-1, grid)\n",
        "\n",
        "        res = 0\n",
        "        for m in range(len(grid)):\n",
        "            for n in range(len(grid[0])):\n",
        "                if grid[m][n] == '1':\n",
        "                    res += 1\n",
        "                    dfs(m,n,grid)\n",
        "        \n",
        "        return res\n",
        "                    \n",
        "        "
      ],
      "metadata": {
        "id": "vvtM3vwy6YiX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "class Solution:\n",
        "    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n",
        "        m = len(heights)\n",
        "        n = len(heights[0])\n",
        "        \n",
        "        visited = set()\n",
        "        deq = deque()\n",
        "        \n",
        "        for i in range(n):\n",
        "            deq.append((0,i))\n",
        "        for i in range(1,m):\n",
        "            deq.append((i,0))\n",
        "        \n",
        "        dirs = [[0,1],[1,0],[-1,0],[0,-1]]\n",
        "        while deq:\n",
        "            x,y = deq.popleft()\n",
        "            if (x,y) in visited:\n",
        "                continue\n",
        "            visited.add((x,y))\n",
        "            \n",
        "            for a,b in dirs:\n",
        "                new_x = x+a\n",
        "                new_y = y+b\n",
        "                \n",
        "                if 0 <= new_x< m and 0<= new_y < n and heights[new_x][new_y] >= heights[x][y]:\n",
        "                    deq.append((new_x,new_y))\n",
        "        #print(visited)\n",
        "        visited_2 = set()\n",
        "        deq = deque()\n",
        "        for i in range(n):\n",
        "            deq.append((m-1,i))\n",
        "        for i in range(m):\n",
        "            deq.append((i,n-1))\n",
        "        \n",
        "        while deq:\n",
        "            x,y = deq.popleft()\n",
        "            if (x,y) in visited_2:\n",
        "                continue\n",
        "            visited_2.add((x,y))\n",
        "            \n",
        "            for a,b in dirs:\n",
        "                new_x = x+a\n",
        "                new_y = y+b\n",
        "                \n",
        "                if 0 <= new_x< m and 0<= new_y < n and heights[new_x][new_y] >= heights[x][y]:\n",
        "                    deq.append((new_x,new_y))\n",
        "        \n",
        "        return visited.intersection(visited_2)\n",
        "\n",
        "class Solution:\n",
        "    def numIslands(self, grid: List[List[str]]) -> int:\n",
        "        dirs = [[0,1],[1,0],[-1,0],[0,-1]]\n",
        "        \n",
        "        m = len(grid)\n",
        "        n = len(grid[0])\n",
        "        \n",
        "        cnt = 0\n",
        "        for i in range(m):\n",
        "            for j in range(n):\n",
        "                if grid[i][j] == '1':\n",
        "                    deq = deque([(i,j)])\n",
        "                    cnt += 1\n",
        "                    while deq:\n",
        "                        x,y = deq.popleft()\n",
        "                        if grid[x][y] == '-1':\n",
        "                            continue\n",
        "                        grid[x][y] = '-1'\n",
        "                        \n",
        "                        for a,b in dirs:\n",
        "                            new_x = x + a\n",
        "                            new_y = y + b\n",
        "                            \n",
        "                            if 0 <= new_x < m and 0 <= new_y < n and grid[new_x][new_y] == '1':\n",
        "                                deq.append((new_x,new_y))\n",
        "        return cnt"
      ],
      "metadata": {
        "id": "lBRoLe248aSB"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "#Apr. 15 2022\n",
        "\n",
        "###Graph\n",
        "\n",
        "https://leetcode.com/problems/longest-consecutive-sequence/\n",
        "\n",
        "https://leetcode.com/problems/alien-dictionary/"
      ],
      "metadata": {
        "id": "Z8hUnBvZx744"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#128\n",
        "class Solution:\n",
        "    def longestConsecutive(self, nums: List[int]) -> int:\n",
        "          \n",
        "        if not nums:\n",
        "            return 0\n",
        "            \n",
        "        nums = set(nums)\n",
        "        res = 0\n",
        "        \n",
        "        for num in nums:\n",
        "            if num-1 not in nums:\n",
        "                temp = 1\n",
        "                while num+1 in nums:\n",
        "                    temp += 1\n",
        "                    num += 1\n",
        "                res = max(temp, res)\n",
        "        \n",
        "        return res\n",
        "                    \n"
      ],
      "metadata": {
        "id": "3GzgTc9BhimZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "'''\n",
        "Category : Disjoint set\n",
        "Union을 할때 rank의 크기를 비교하여 (연속된 시퀀스) 저장, rank 가 tree의 높이가 아니라 사이즈\n",
        "TC : O(N)\n",
        "'''\n",
        "class Solution:\n",
        "    def longestConsecutive(self, nums: List[int]) -> int:\n",
        "        class Node:\n",
        "            def __init__(self, rank):\n",
        "                self.parent = self\n",
        "                self.rank = rank\n",
        "        \n",
        "        def union(x, y):\n",
        "            x = find(x)\n",
        "            y = find(y)\n",
        "            if x != y:\n",
        "                if x.rank > y.rank:\n",
        "                    y.parent = x\n",
        "                    x.rank += y.rank\n",
        "                else:\n",
        "                    x.parent = y\n",
        "                    y.rank += x.rank\n",
        "        \n",
        "        def find(x):\n",
        "            if x.parent != x:\n",
        "                x.parent = find(x.parent)\n",
        "            return x.parent\n",
        "        \n",
        "        length = len(nums)\n",
        "        if length <= 1:\n",
        "            return length\n",
        "        \n",
        "        map_ = dict()\n",
        "        for i in range(length):\n",
        "            if nums[i] not in map_:\n",
        "                map_[nums[i]] = Node(1)\n",
        "        \n",
        "        res = 1\n",
        "        for num in nums:\n",
        "            if num + 1 in map_:\n",
        "                union(map_[num], map_[num+1])\n",
        "            if num - 1 in map_:\n",
        "                union(map_[num], map_[num-1])\n",
        "            node = find(map_[num])\n",
        "            res = max(res, node.rank)\n",
        "            \n",
        "        return res\n",
        "'''\n",
        "수정중입니다. 풀어서 다시올릴게용.\n",
        "'''\n",
        "class Solution:\n",
        "    def alienOrder(self, words: List[str]) -> str:\n",
        "        def dfs(i, res):\n",
        "            if visited[i]:\n",
        "                return (res,False)\n",
        "            visited[i] = True\n",
        "            path[i] = True\n",
        "            for nei in graph[i]:\n",
        "                if i == nei:\n",
        "                    continue\n",
        "                if path[nei] or dfs(i, res)[1]:\n",
        "                    return (res, True)\n",
        "            path[i] = False\n",
        "            res += chr(ord('a') + i)\n",
        "            return (res, False)\n",
        "        \n",
        "        graph = defaultdict(list)\n",
        "        visited = [False] * 26\n",
        "        path = [False] * 26\n",
        "        for word in words:\n",
        "            for c in word:\n",
        "                graph[ord(c) - ord('a')].append(ord(c) - ord('a'))\n",
        "        for i in range(len(words)-1):\n",
        "            min_ = min(len(words[i]), len(words[i+1]))\n",
        "            for j in range(min_):\n",
        "                if words[i][j] != words[i+1][j]:\n",
        "                    graph[ord(words[i][j]) - ord('a')].append(ord(words[i+1][j]) - ord('a'))\n",
        "                    break\n",
        "            if j == min_ and len(words[i]) > len(words[i+1]):\n",
        "                return \"\"\n",
        "        res = \"\"\n",
        "        for i in range(26):\n",
        "            #if len(graph[chr(ord('a') + i)]) > 0\n",
        "            if len(graph[i]) > 0:\n",
        "                temp = dfs(i, res)\n",
        "                res = temp[0]\n",
        "                if temp[1]:\n",
        "                    return \"\"\n",
        "        res = res[::-1]\n",
        "        return res"
      ],
      "metadata": {
        "id": "RBwpp9sQiBCZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def longestConsecutive(self, nums: List[int]) -> int:\n",
        "        if len(nums) < 2:\n",
        "            return len(nums)\n",
        "        \n",
        "        nums = set(nums)\n",
        "        ans = 0\n",
        "        for n in nums:\n",
        "            if n-1 not in nums:\n",
        "                cnt = 1\n",
        "                while n+1 in nums:\n",
        "                    cnt += 1\n",
        "                    n += 1\n",
        "                ans = max(ans,cnt)\n",
        "        return ans"
      ],
      "metadata": {
        "id": "MZBQYkOEjV7P"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "LoEwy7FllfTY"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 19 2022\n",
        "https://leetcode.com/problems/graph-valid-tree/\n",
        "\n",
        "https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/\n",
        "\n",
        "Graph"
      ],
      "metadata": {
        "id": "NuHd9TCplfpD"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class UnionFind:\n",
        "    def __init__(self, n):\n",
        "        self.arr = list(range(n))\n",
        "        self.weight = [1] * n\n",
        "    \n",
        "    def find(self, i):\n",
        "        while i != self.arr[i]:\n",
        "            i = self.arr[i]\n",
        "            \n",
        "        return i\n",
        "    \n",
        "    def union(self, a, b):\n",
        "        rootA = self.find(a)\n",
        "        rootB = self.find(b)\n",
        "        \n",
        "        if rootA == rootB: # same parent\n",
        "            return False\n",
        "        elif self.weight[rootA] >= self.weight[rootB]:\n",
        "            self.arr[rootB] = rootA\n",
        "            self.weight[rootA] += self.weight[rootB]\n",
        "            return True\n",
        "        else:\n",
        "            self.arr[rootA] = rootB\n",
        "            self.weight[rootB] += self.weight[rootA]\n",
        "            return True\n",
        "        \n",
        "class Solution:\n",
        "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
        "        uf = UnionFind(n)\n",
        "        \n",
        "        for s,e in edges:\n",
        "            re = uf.union(s,e)\n",
        "            if re == False:\n",
        "                return False\n",
        "        parent = uf.find(0)\n",
        "        return uf.weight[parent] == n\n",
        "\n",
        "\n",
        "###############################\n",
        "class UnionFind:\n",
        "    def __init__(self, n):\n",
        "        self.p = list(range(n))\n",
        "        self.w = [1] * n\n",
        "    \n",
        "    def find(self, i):\n",
        "        while i != self.p[i]:\n",
        "            i = self.p[i]\n",
        "        return i\n",
        "    \n",
        "    def union(self, a,b):\n",
        "        rootA = self.find(a)\n",
        "        rootB = self.find(b)\n",
        "        \n",
        "        if rootA == rootB:\n",
        "            return\n",
        "        if self.w[rootA] >= self.w[rootB]:\n",
        "            self.p[rootB] = rootA\n",
        "            self.w[rootA] += self.w[rootB]\n",
        "        else:\n",
        "            self.p[rootA] = rootB\n",
        "            self.w[rootB] += self.w[rootA]\n",
        "        \n",
        "class Solution:\n",
        "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
        "        uf = UnionFind(n)\n",
        "        \n",
        "        for s,e in edges:\n",
        "            uf.union(s,e)\n",
        "        \n",
        "        parent_set = set()\n",
        "        for i in range(n):\n",
        "            parent_set.add(uf.find(i))\n",
        "        \n",
        "        return len(parent_set)\n",
        "\n",
        "      "
      ],
      "metadata": {
        "id": "1-zULWFq5eAp"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "\n",
        "#261\n",
        "class Solution:\n",
        "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
        "               \n",
        "        graph = collections.defaultdict(list)\n",
        "        \n",
        "        for a, b in edges:\n",
        "            graph[a].append(b)\n",
        "            graph[b].append(a)\n",
        "        \n",
        "        seen = set()\n",
        "        \n",
        "        def dfs(curr, prev):\n",
        "            if curr in seen:\n",
        "                return False\n",
        "            \n",
        "            seen.add(curr)  \n",
        "            for nei in graph[curr]:\n",
        "                if nei == prev:\n",
        "                    continue\n",
        "                if not dfs(nei, curr):\n",
        "                    return False        \n",
        "            return True\n",
        "\n",
        "        return dfs(0, -1) and len(seen) == n\n",
        "            \n",
        "    \n",
        "#323\n",
        "class Solution:\n",
        "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
        "        \n",
        "        graph = collections.defaultdict(list)\n",
        "        \n",
        "        for a, b in edges:\n",
        "            graph[a].append(b)\n",
        "            graph[b].append(a)\n",
        "        \n",
        "        seen = set()\n",
        "        res = 0 \n",
        "        \n",
        "        def dfs(node):\n",
        "            if node not in graph:\n",
        "                return\n",
        "            seen.add(node)\n",
        "            for nei in graph[node]:\n",
        "                if nei not in seen:\n",
        "                    dfs(nei)\n",
        "        \n",
        "\n",
        "        for i in range(n):\n",
        "            if i not in seen:\n",
        "                dfs(i)\n",
        "                res += 1\n",
        "                \n",
        "        return res"
      ],
      "metadata": {
        "id": "gxpcV9-krfC0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "from collections import defaultdict\n",
        "class Solution:\n",
        "    def validTree(self, n: int, edges: List[List[int]]) -> bool:\n",
        "        \n",
        "        def dfs(graph, i, visited):\n",
        "            if visited[i]==True:\n",
        "                return False\n",
        "            \n",
        "            visited[i] = True\n",
        "            if i in graph:\n",
        "                for nei in graph[i]:\n",
        "                    graph[nei].remove(i)\n",
        "                    if dfs(graph, nei, visited)==False:\n",
        "                        return False\n",
        "            return True\n",
        "        \n",
        "        graph = defaultdict(list)\n",
        "        # defaultdict(list) 로 모든 edge들을 연결하여 graph를 만듬\n",
        "        for edge in edges:\n",
        "            graph[edge[0]].append(edge[1])\n",
        "            graph[edge[1]].append(edge[0])\n",
        "        \n",
        "        # visited\n",
        "        visited = [False] * n \n",
        "        if dfs(graph, 0, visited) == False:\n",
        "            return False\n",
        "        \n",
        "        for i in range(n):\n",
        "            if visited[i]==False:\n",
        "                return False\n",
        "        \n",
        "        return True\n",
        "\n",
        "'''\n",
        "'''\n",
        "from collections import defaultdict\n",
        "class Solution:\n",
        "    def countComponents(self, n: int, edges: List[List[int]]) -> int:\n",
        "        def dfs(i):\n",
        "            visited[i] = True\n",
        "            \n",
        "            for nei in graph[i]:\n",
        "                if visited[nei] == False:\n",
        "                    dfs(nei)\n",
        "            \n",
        "        \n",
        "        \n",
        "        \n",
        "        graph = defaultdict(list)\n",
        "        res = 0\n",
        "        for edge in edges:\n",
        "            graph[edge[0]].append(edge[1])\n",
        "            graph[edge[1]].append(edge[0])\n",
        "        \n",
        "        visited = [False] * n\n",
        "        for i in range(n):\n",
        "            if visited[i] == False:\n",
        "                res += 1\n",
        "                dfs(i)\n",
        "        \n",
        "        return res"
      ],
      "metadata": {
        "id": "kqrHJXc2XAAi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 20 2022\n",
        "- Insert Interval - https://leetcode.com/problems/insert-interval/\n",
        "- Merge Intervals - https://leetcode.com/problems/merge-intervals/\n",
        "\n",
        "###Intervel"
      ],
      "metadata": {
        "id": "G1vtbpmuhepz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's Code\n",
        "\n",
        "class Solution:\n",
        "    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: \n",
        "        res = []\n",
        "        for interval in intervals:\n",
        "            if interval[1] < newInterval[0] and interval[0] < newInterval[0]:\n",
        "                res.append(interval)\n",
        "            elif interval[0] > newInterval[1]:\n",
        "                res.append(newInterval)\n",
        "                newInterval = interval\n",
        "            elif newInterval[0] > interval[1]:\n",
        "                res.append(newInterval)\n",
        "            else:\n",
        "                newInterval[0] = min(newInterval[0],interval[0])\n",
        "                newInterval[1] = max(newInterval[1],interval[1])\n",
        "        res.append(newInterval)\n",
        "        return res\n",
        "\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "        start, end = -1, -1\n",
        "        intervals.sort(key = lambda x:x[0])\n",
        "        res = []\n",
        "        for interval in intervals:\n",
        "            if end < interval[0]:\n",
        "                if start != -1 and end != -1:\n",
        "                    res.append([start,end])\n",
        "                start = interval[0]\n",
        "                end = interval[1]\n",
        "            else:\n",
        "                end = max(end,interval[1])\n",
        "        res.append([start,end])\n",
        "        return res\n"
      ],
      "metadata": {
        "id": "Q1_rfd4EhObq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#Insert\n",
        "class Solution:\n",
        "    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n",
        "        \n",
        "        if not intervals:\n",
        "            return [newInterval]\n",
        "        \n",
        "        res = []\n",
        "        \n",
        "        for i, interval in enumerate(intervals):\n",
        "            if  newInterval[1] < interval[0]:\n",
        "                res.append(newInterval)\n",
        "                return res + intervals[i:]\n",
        "            elif newInterval[0] <= interval[1]:\n",
        "                newInterval = [min(newInterval[0], interval[0]), max(newInterval[1], interval[1])]\n",
        "            else:\n",
        "                res.append(interval)\n",
        "        \n",
        "        res.append(newInterval)\n",
        "        \n",
        "        return res\n",
        "\n",
        "#Merge\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\\\n",
        "        \n",
        "        intervals.sort(key=lambda x:x[0])\n",
        "        \n",
        "        res = []\n",
        "        \n",
        "        for interval in intervals:\n",
        "            if not res:\n",
        "                res.append(interval)\n",
        "            else:\n",
        "                top = res[-1]\n",
        "                if interval[0] <= top[1]:\n",
        "                    res[-1] = [top[0], max(top[1], interval[1])]\n",
        "                else:\n",
        "                    res.append(interval)\n",
        "        \n",
        "        return res\n",
        "        "
      ],
      "metadata": {
        "id": "QAiLWtNH-q0H"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n",
        "        if not intervals:\n",
        "            return [newInterval]\n",
        "        new_start, new_end = newInterval\n",
        "        \n",
        "        ans = []\n",
        "        for i in range(len(intervals)):\n",
        "            start, end = intervals[i]\n",
        "            if end < new_start:     # [1 3] new[4 5]\n",
        "                ans.append([start,end])\n",
        "                idx = i+1 # for next stage\n",
        "            else:                   # overlapped\n",
        "                idx = i\n",
        "                break\n",
        "        \n",
        "        ans.append(newInterval)\n",
        "        \n",
        "        for i in range(idx, len(intervals)):\n",
        "            start, end = intervals[i]\n",
        "            if new_end < start:     # new[4 5] [6 7]\n",
        "                idx = i\n",
        "                break\n",
        "            else:                   # overlapped\n",
        "                ans[-1][0] = min(new_start, start)\n",
        "                ans[-1][1] = max(new_end, end)\n",
        "                new_start = ans[-1][0]\n",
        "                new_end = ans[-1][1]\n",
        "                idx = i+1\n",
        "        \n",
        "        for i in range(idx, len(intervals)):\n",
        "            ans.append(intervals[i]) # new[4 5] [6 7]\n",
        "            \n",
        "        return ans\n",
        "\n",
        "class Solution:\n",
        "    def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n",
        "        intervals.sort(key= lambda x:(x[1]))\n",
        "        #print(intervals)\n",
        "        ans = [intervals[0]]\n",
        "        for s, e in intervals:\n",
        "            if s <= ans[-1][0]:\n",
        "                while ans and s <= ans[-1][0]:\n",
        "                    ans.pop()\n",
        "                \n",
        "            if ans and ans[-1][1] >= s: # 1 5  4 6\n",
        "                ans[-1][1] = e\n",
        "            else:\n",
        "                ans.append([s,e])\n",
        "        return ans\n"
      ],
      "metadata": {
        "id": "3kMP17iq_lkt"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 22 2022\n",
        "- Non-overlapping Intervals - https://leetcode.com/problems/non-overlapping-intervals/\n",
        "- Meeting Rooms II (Leetcode Premium) - https://leetcode.com/problems/meeting-rooms-ii/\n",
        "\n",
        "###Intervel"
      ],
      "metadata": {
        "id": "tPjnwmwneDQs"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "#Non-overlapping\n",
        "class Solution:\n",
        "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:      \n",
        "        res = 0    \n",
        "        intervals.sort(key=lambda x:x[0])\n",
        "        \n",
        "        prev_end = intervals[0][1]\n",
        "        \n",
        "        for interval in intervals[1:]:\n",
        "            \n",
        "            if interval[0] < prev_end:\n",
        "                prev_end = min(prev_end, interval[1])\n",
        "                res += 1\n",
        "            else:\n",
        "                prev_end = interval[1]\n",
        "        \n",
        "        return res\n",
        "\n",
        "#Meeting rooms\n",
        "class Solution:\n",
        "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
        "        \n",
        "        intervals.sort(key=lambda x:x[0])\n",
        "        \n",
        "        rooms = []\n",
        "        heapq.heappush(rooms, intervals[0][-1])\n",
        "        \n",
        "        for interval in intervals[1:]: \n",
        "            if interval[0] < rooms[0]:\n",
        "                heapq.heappush(rooms, interval[1])\n",
        "            else:\n",
        "                heapq.heappop(rooms)\n",
        "                heapq.heappush(rooms, interval[1])\n",
        " \n",
        "        return len(rooms)"
      ],
      "metadata": {
        "id": "R4mPbE6iHUaN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# YS\n",
        "class Solution:\n",
        "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
        "        intervals.sort(key=lambda x : x[1])\n",
        "        \n",
        "        start, end = intervals[0]\n",
        "        count = 0\n",
        "        \n",
        "        for new_start, new_end in intervals[1:]:\n",
        "            if new_start < end: # 2 '4' 6 '8'\n",
        "                count += 1\n",
        "            else:\n",
        "                end = new_end\n",
        "        return count\n",
        "\n",
        "class Solution:\n",
        "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
        "        intervals.sort(key = lambda x : (x[0],-x[1]))\n",
        "        \n",
        "        heap = []\n",
        "        ans = 0\n",
        "        for s,e in intervals:\n",
        "            if not heap:\n",
        "                heap = [e]\n",
        "            elif heap[0] <= s:\n",
        "                heapq.heappop(heap)\n",
        "                heapq.heappush(heap,e)\n",
        "            else:\n",
        "                heapq.heappush(heap,e)\n",
        "            \n",
        "        ans = len(heap)\n",
        "        return ans"
      ],
      "metadata": {
        "id": "UIQXNTzOIJZU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "class Solution:\n",
        "    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:\n",
        "        intervals.sort(key = lambda x:x[0])\n",
        "        res = 0\n",
        "        temp = intervals[0][1]\n",
        "        for i in range(1, len(intervals)):\n",
        "            if intervals[i][0] < temp:\n",
        "                res+= 1\n",
        "                temp = min(intervals[i][1], temp)\n",
        "            else:\n",
        "                temp = intervals[i][1]\n",
        "        \n",
        "            \n",
        "        return res\n",
        "'''\n",
        "'''\n",
        "class Solution:\n",
        "    def minMeetingRooms(self, intervals: List[List[int]]) -> int:\n",
        "        intervals.sort(key = lambda x:x[0])\n",
        "        rooms = []\n",
        "        heapq.heappush(rooms, intervals[0][1])\n",
        "        \n",
        "        for i in range(1, len(intervals)):\n",
        "            if rooms[0] <= intervals[i][0]:\n",
        "                heapq.heappop(rooms)\n",
        "            \n",
        "            heapq.heappush(rooms, intervals[i][1])\n",
        "        \n",
        "        return len(rooms)"
      ],
      "metadata": {
        "id": "7BQTlUMHhWWZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 25 2022\n",
        "- Reverse a Linked List - https://leetcode.com/problems/reverse-linked-list/\n",
        "- Detect Cycle in a Linked List - https://leetcode.com/problems/linked-list-cycle/\n",
        "- Merge Two Sorted Lists - https://leetcode.com/problems/merge-two-sorted-lists/\n",
        "- Merge K Sorted Lists - https://leetcode.com/problems/merge-k-sorted-lists/\n",
        "\n",
        "###Linked List (Easy 3개, Hard 1개 : 주말찬스)"
      ],
      "metadata": {
        "id": "uPPjgL1Tee6E"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's mcode\n",
        "\n",
        "#Reverse Linked List\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "class Solution:\n",
        "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        pre = None\n",
        "        \n",
        "        while head:\n",
        "            curr = head\n",
        "            head = head.next\n",
        "            curr.next = pre\n",
        "            pre = curr\n",
        "        return pre\n",
        "\n",
        "#\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, x):\n",
        "#         self.val = x\n",
        "#         self.next = None\n",
        "\n",
        "class Solution:\n",
        "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
        "        '''\n",
        "        plus, minus = 0, 0\n",
        "        while head:\n",
        "            if head.val>=0:\n",
        "                check = 1 << head.val\n",
        "                if check & plus != 0:\n",
        "                    return True\n",
        "                plus |= check\n",
        "            else:\n",
        "                check = 1 << (head.val * -1)\n",
        "                if check & minus != 0:\n",
        "                    return True\n",
        "                minus |= check\n",
        "            head = head.next\n",
        "        return False\n",
        "        '''\n",
        "        slow = head\n",
        "        fast = head\n",
        "        while fast != None and fast.next != None:\n",
        "            slow = slow.next\n",
        "            fast = fast.next.next\n",
        "            if fast == slow:\n",
        "                return True\n",
        "        return False\n",
        "\n",
        "#Merge Two Sorted Lists\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "class Solution:\n",
        "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        temp = ListNode()\n",
        "        res = temp\n",
        "        while list1 or list2:\n",
        "            a = list1.val if list1 else 102\n",
        "            b = list2.val if list2 else 102\n",
        "                \n",
        "            if a < b:\n",
        "                temp.next = ListNode(a)\n",
        "                list1 = list1.next\n",
        "            else:\n",
        "                temp.next = ListNode(b)\n",
        "                list2 = list2.next\n",
        "            temp = temp.next\n",
        "        return res.next\n",
        "\n",
        "#Merge k Sorted Lists\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "\n",
        "from queue import PriorityQueue\n",
        "class Solution:\n",
        "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
        "        class Data:\n",
        "            def __init__(self, node):\n",
        "                self.val = node.val\n",
        "                self.node = node\n",
        "            \n",
        "            def __lt__(self, other):\n",
        "                if self.val == other.val:\n",
        "                    return 1\n",
        "                return self.val < other.val\n",
        "        \n",
        "        head = ListNode(0)\n",
        "        tail = head\n",
        "        pq = PriorityQueue()\n",
        "        for node in lists:\n",
        "            if node:\n",
        "                pq.put(Data(node))\n",
        "        while not pq.empty():\n",
        "            data = pq.get()\n",
        "            tail.next = ListNode(data.val)\n",
        "            tail = tail.next\n",
        "            node = data.node.next\n",
        "            if node:\n",
        "                pq.put(Data(node))\n",
        "        return head.next"
      ],
      "metadata": {
        "id": "Gwmm7qrlb0XN"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#JH\n",
        "class Solution:\n",
        "    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        \n",
        "        prev = None\n",
        "        \n",
        "        while head:\n",
        "            next_ = head.next\n",
        "            head.next = prev\n",
        "            prev = head\n",
        "            head = next_\n",
        "        \n",
        "        return prev\n",
        "\n",
        "class Solution:\n",
        "    def hasCycle(self, head: Optional[ListNode]) -> bool:\n",
        "        \n",
        "        \n",
        "        slow, fast = head, head\n",
        "        \n",
        "        while fast and fast.next:\n",
        "            slow = slow.next\n",
        "            fast = fast.next.next\n",
        "            \n",
        "            if slow == fast:\n",
        "                return True\n",
        "        \n",
        "        return False\n",
        "\n",
        "class Solution:\n",
        "    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n",
        "        \n",
        "        cur = ListNode(None)\n",
        "        res = cur\n",
        "        \n",
        "        while list1 and list2:\n",
        "            \n",
        "            if list1.val <= list2.val:\n",
        "                cur.next = list1\n",
        "                list1 = list1.next\n",
        "            \n",
        "            else:\n",
        "                cur.next = list2\n",
        "                list2 = list2.next\n",
        "            \n",
        "            cur = cur.next\n",
        "        \n",
        "        if list1: \n",
        "            cur.next = list1\n",
        "        \n",
        "        elif list2:\n",
        "            cur.next = list2\n",
        "        \n",
        "        return res.next\n",
        "\n",
        "class Solution:\n",
        "    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:\n",
        "        #merge sort\n",
        "        \n",
        "        if not lists or len(lists) == 0:\n",
        "            return None\n",
        "        \n",
        "        while len(lists) > 1:\n",
        "            mergedLists = []\n",
        "\n",
        "            for i in range(0,len(lists),2):\n",
        "                l1 = lists[i]\n",
        "                l2 = lists[i+1] if (i+1) < len(lists) else None\n",
        "                mergedLists.append(self.mergeLists(l1, l2))\n",
        "   ` `         lists = mergedLists\n",
        "            \n",
        "        return lists[0]\n",
        "    \n",
        "    def mergeLists(self, l1, l2):\n",
        "        cur = ListNode(None)\n",
        "        res = cur\n",
        "        \n",
        "        while l1 and l2:\n",
        "            if l1.val < l2.val:\n",
        "                cur.next = l1\n",
        "                l1 = l1.next\n",
        "            else:\n",
        "                cur.next = l2\n",
        "                l2 = l2.next\n",
        "            cur = cur.next\n",
        "        \n",
        "        if l1:\n",
        "            cur.next = l1\n",
        "        if l2: \n",
        "            cur.next = l2\n",
        "            \n",
        "        return res.next"
      ],
      "metadata": {
        "id": "n4T2Wt1-oaUC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 26 2022\n",
        "- Remove Nth Node From End Of List - https://leetcode.com/problems/remove-nth-node-from-end-of-list/\n",
        "- Reorder List - https://leetcode.com/problems/reorder-list/\n",
        "\n",
        "###Linked List"
      ],
      "metadata": {
        "id": "WefwYax_fb01"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#Minsu's code\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "class Solution:\n",
        "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
        "        res = ListNode(0)\n",
        "        res.next = head\n",
        "        temp = head\n",
        "        cnt = 0\n",
        "        while temp:\n",
        "            temp = temp.next\n",
        "            cnt += 1\n",
        "        for i in range(cnt-n-1):\n",
        "            head = head.next\n",
        "        if cnt-n==0:\n",
        "            return head.next\n",
        "        head.next = head.next.next\n",
        "        return res.next\n",
        "\n",
        "# Definition for singly-linked list.\n",
        "# class ListNode:\n",
        "#     def __init__(self, val=0, next=None):\n",
        "#         self.val = val\n",
        "#         self.next = next\n",
        "class Solution:\n",
        "    def reorderList(self, head: Optional[ListNode]) -> None:\n",
        "        \"\"\"\n",
        "        Do not return anything, modify head in-place instead.\n",
        "        \"\"\"\n",
        "        stack = []\n",
        "        temp = head\n",
        "        cnt = 0\n",
        "        \n",
        "        while temp:\n",
        "            stack.append(temp)\n",
        "            temp = temp.next\n",
        "            cnt += 1\n",
        "        \n",
        "        temp = head\n",
        "        \n",
        "        for i in range(cnt//2):\n",
        "            curr = temp.next\n",
        "            temp.next = stack[-1]\n",
        "            stack.pop().next = curr\n",
        "            temp = temp.next.next\n",
        "        \n",
        "        temp.next = None #싸이클 끊어주기위해서\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "mr3dxUqxn92C"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 27 2022\n",
        "- Set Matrix Zeroes - https://leetcode.com/problems/set-matrix-zeroes/\n",
        "- Spiral Matrix - https://leetcode.com/problems/spiral-matrix/\n",
        "\n",
        "###Matrix"
      ],
      "metadata": {
        "id": "yIy8iJ3xf6hy"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 28 2022\n",
        "- Rotate Image - https://leetcode.com/problems/rotate-image/\n",
        "- Word Search - https://leetcode.com/problems/word-search/\n",
        "\n",
        "###Matrix"
      ],
      "metadata": {
        "id": "BLARkcEigEBi"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# APR. 29 2022\n",
        "- Longest Substring Without Repeating Characters - https://leetcode.com/problems/longest-substring-without-repeating-characters/\n",
        "- Longest Repeating Character Replacement - https://leetcode.com/problems/longest-repeating-character-replacement/\n",
        "\n",
        "###String"
      ],
      "metadata": {
        "id": "BRNR4904gNwx"
      }
    }
  ]
}