algorithm/List/dynamic_array_ones_minus_zeros.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[문제]  \n",
    "![algorithm-problem.png](../../img/algorithm-231213-01.png)  \n",
    "link: https://leetcode.com/problems/difference-between-ones-and-zeros-in-row-and-column"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[풀이]  \n",
    "- 부르트포스로 각 row, col에 있는 1의 수를 더한다.  \n",
    "- `diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj`  \n",
    "    ` = (onesRowi - zerosRowi) + (onesColj - zerosColj)`  \n",
    "    ` = (2 * onesRowi - rowLen) + (2 * onesColj - colLen)`  \n",
    "    을 이용해 계산해준다. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        OnesRow=defaultdict(int)\n",
    "        OnesCol=defaultdict(int)\n",
    "        for i, r in enumerate(grid):\n",
    "            OnesRow[i]=sum(r)\n",
    "            for j, c in enumerate(r):\n",
    "                OnesCol[j]+=c\n",
    "                \n",
    "        rowNum = len(grid)\n",
    "        colNum = len(grid[0])\n",
    "        for i in range(rowNum):\n",
    "            for j in range(colNum):\n",
    "                grid[i][j] = 2*OnesRow[i] + 2*OnesCol[j] - rowNum - colNum\n",
    "        \n",
    "        return grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "cf) \n",
    "아래는 약간 멋지게 생긴 풀이.  \n",
    "count 함수 만들어서 zip(*grid) 사용한 거랑, product 함수 사용한 것이 fancy했다.   \n",
    "실제로 실행속도와 메모리 사용도 더 효율적이었다.  \n",
    "  \n",
    "[상위 98%의 beats]  \n",
    "![algorithm-problem.png](../../img/algorithm-231213-02.png)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def count(nums) : return 2*sum(nums)-len(nums)       # [1] count score for a list of numbers\n",
    "            \n",
    "        rows = list(map(count, grid))                        # [2] count scores for rows\n",
    "        cols = list(map(count, zip(*grid)))                  # [3] count scores for columns (transpose)\n",
    "\n",
    "        for i,j in product(range(m), range(n)):              # [4] update the input matrix with\n",
    "            grid[i][j] = rows[i] + cols[j]                   #     sums of precomputed scores\n",
    "                \n",
    "        return grid"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}