\n \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub294 \ud2b9\uc815 \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 “\ubb3c\uc758 \uc591”\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uc774\ub97c \ud1b5\ud574 \ud30c\uc774\uc36c \ucf54\ub4dc\ub97c \uc791\uc131\ud558\ub294 \ubc29\ubc95\uacfc \uc54c\uace0\ub9ac\uc998\uc801 \uc0ac\uace0\uc758 \uc911\uc694\uc131\uc5d0 \ub300\ud574 \uc54c\ub824\ub4dc\ub9ac\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n
\n \uc5ec\ub7ec\ubd84\uc740 \ud55c\uac1c\uc758 \uc218\uc870\uc5d0\uc11c \ubb3c\uc758 \uc591\uc744 \uacc4\uc0b0\ud574\uc57c \ud569\ub2c8\ub2e4. \uc218\uc870\uc758 \ub192\uc774\ub97c \ub098\ud0c0\ub0b4\ub294 \uc815\uc218 \ubc30\uc5f4 \n \ube44\uac00 \ub0b4\ub9b0 \ud6c4, \uac01 \ube14\ub85d \uc0ac\uc774\uc5d0 \uace0\uc778 \ubb3c\uc758 \uc591\uc744 \uacc4\uc0b0\ud558\ub294 \ud568\uc218\ub97c \ub9cc\ub4e4\uace0, \ucd1d \uace0\uc778 \ubb3c\uc758 \uc591\uc744 \ubc18\ud658\ud574\uc57c \ud569\ub2c8\ub2e4.\n<\/p>\n \uc124\uba85: \uace0\uc778 \ubb3c\uc758 \uc591\uc740 6\uc785\ub2c8\ub2e4.<\/p>\n \uc124\uba85: \uace0\uc778 \ubb3c\uc758 \uc591\uc740 9\uc785\ub2c8\ub2e4.<\/p>\n \n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub450 \uac00\uc9c0 \uc8fc\uc694 \ud3ec\uc778\ud2b8\ub97c \uc774\ud574\ud574\uc57c \ud569\ub2c8\ub2e4:\n<\/p>\n \n \uc774\ub97c \uc704\ud574 \uc6b0\ub9ac\ub294 \ub450 \uac1c\uc758 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud560 \uac83\uc785\ub2c8\ub2e4. \ud558\ub098\ub294 \uc67c\ucabd\uc5d0\uc11c\ubd80\ud130 \uac01 \uc704\uce58\uc758 \ucd5c\ub300 \ub192\uc774\ub97c \uc800\uc7a5\ud558\uace0, \ub2e4\ub978 \ud558\ub098\ub294 \uc624\ub978\ucabd\uc740 \ucd5c\ub300 \ub192\uc774\ub97c \uc800\uc7a5\ud569\ub2c8\ub2e4.\n<\/p>\n \n \uc774\uc81c \uc774\ub97c \ubc14\ud0d5\uc73c\ub85c \uc2e4\uc81c \ucf54\ub4dc\ub97c \uc791\uc131\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n<\/p>\n \n 1. \n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)\uc785\ub2c8\ub2e4. \ub450 \uac1c\uc758 \ubc30\uc5f4\uc744 \ub9cc\ub4e4\uc5b4 \uac01\uac01\uc758 \ucd5c\ub300 \ub192\uc774\ub97c \uacc4\uc0b0\ud558\ub294 \ub370 O(n) \uc2dc\uac04\uc774 \uc18c\uc694\ub418\uba70, \ub2e4\uc2dc \ubc18\ubcf5\uc801\uc73c\ub85c \uace0\uc778 \ubb3c\uc758 \uc591\uc744 \uce21\uc815\ud558\ub294 \ub370 O(n) \uc2dc\uac04\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.\n<\/p>\n \n \ubaa8\ub4e0 \ub2e8\uacc4\ub97c \ud569\uce58\uba74 \ucd1d O(n)\uc785\ub2c8\ub2e4.\n<\/p>\n \n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \ubb3c\uc758 \uc591\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc5d0 \ub300\ud574 \uc2ec\ub3c4 \uc788\uac8c \ud559\uc2b5\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \uc774 \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud480\uc774\uc758 \ub300\ud45c\uc801\uc778 \uc608\ub85c, \ub2e4\uc591\ud55c \ubcc0\ud615\uc774 \uc874\uc7ac\ud569\ub2c8\ub2e4. \uc5ec\ub7ec\ubd84\ub4e4\ub3c4 \uc774\uc640 \uc720\uc0ac\ud55c \ubb38\uc81c\ub97c \uc5f0\uc2b5\ud558\uba74\uc11c \ucf54\ub4dc \uc791\uc131 \ub2a5\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n<\/p>\n \n \ub2e4\uc74c\uacfc \uac19\uc740 \ubcc0\ud615 \ubb38\uc81c\ub97c \uc5f0\uc2b5\ud574\ubcf4\ub294 \uac83\uc744 \ucd94\ucc9c\ud569\ub2c8\ub2e4:\n<\/p>\nheight<\/code>\uac00 \uc8fc\uc5b4\uc84c\uc2b5\ub2c8\ub2e4. \uc218\uc870\ub294 \uc218\ud3c9\uc73c\ub85c \ubc30\uc5f4\ub41c \ube14\ub85d\uc73c\ub85c \uad6c\uc131\ub418\uc5b4 \uc788\uc73c\uba70, \uac01 \ube14\ub85d\uc758 \ub192\uc774\ub294 height[i]<\/code>\ub85c \ud45c\ud604\ub429\ub2c8\ub2e4.\n<\/p>\n\uc785\ub825<\/h3>\n
\n
height<\/code>: \uc591\uc758 \uc815\uc218\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ub9ac\uc2a4\ud2b8. (1 \u2264 height.length \u2264 2 * 10^4, 0 \u2264 height[i] \u2264 10^5)<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\n
\uc608\uc81c<\/h2>\n
\uc608\uc81c 1<\/h3>\n
\uc785\ub825: height = [0,1,0,2,1,0,1,3,2,1,2,1]\n\ucd9c\ub825: 6<\/code><\/pre>\n\uc608\uc81c 2<\/h3>\n
\uc785\ub825: height = [4,2,0,3,2,5]\n\ucd9c\ub825: 9<\/code><\/pre>\n\ubb38\uc81c \ud574\uacb0 \uc811\uadfc\ubc95<\/h2>\n
\n
min(\uc67c\ucabd \ucd5c\ub300 \ub192\uc774, \uc624\ub978\ucabd \ucd5c\ub300 \ub192\uc774) - \ud604\uc7ac \ub192\uc774<\/code>\ub85c \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\n<\/ol>\n\ucf54\ub4dc \uad6c\ud604<\/h2>\n
def trap(height):\n if not height:\n return 0\n\n n = len(height)\n left_max = [0] * n\n right_max = [0] * n\n\n # \uc67c\ucabd \ucd5c\ub300 \ub192\uc774 \uacc4\uc0b0\n left_max[0] = height[0]\n for i in range(1, n):\n left_max[i] = max(left_max[i - 1], height[i])\n\n # \uc624\ub978\ucabd \ucd5c\ub300 \ub192\uc774 \uacc4\uc0b0\n right_max[n - 1] = height[n - 1]\n for i in range(n - 2, -1, -1):\n right_max[i] = max(right_max[i + 1], height[i])\n\n # \uace0\uc778 \ubb3c\uc758 \uc591 \uacc4\uc0b0\n water_trapped = 0\n for i in range(n):\n water_trapped += min(left_max[i], right_max[i]) - height[i]\n\n return water_trapped\n\n# \uc608\uc81c \uc2e4\ud589\nprint(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1])) # \ucd9c\ub825: 6\nprint(trap([4, 2, 0, 3, 2, 5])) # \ucd9c\ub825: 9\n<\/code><\/pre>\n\ucf54\ub4dc \uc124\uba85<\/h2>\n
trap(height)<\/code>: \uc774 \ud568\uc218\uc5d0\uc11c\ub294 \ubb3c\uc744 trap(\ud3ec\ud68d)\ud558\ub294 \uc591\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.
\n 2. \uc785\ub825\uc73c\ub85c height<\/code> \ub9ac\uc2a4\ud2b8\ub97c \ubc1b\uace0, \uc774\ub97c \ud1b5\ud574 \ubb3c\uc758 \uc591\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.
\n 3. \ube48 \ub9ac\uc2a4\ud2b8\uc778 \uacbd\uc6b0 0\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.
\n 4. \uac01 \uc778\ub371\uc2a4\uc5d0\uc11c \uc67c\ucabd \ucd5c\ub300 \ub192\uc774\ub97c \uacc4\uc0b0\ud558\uace0, \uc624\ub978\ucabd \ucd5c\ub300 \ub192\uc774\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.
\n 5. \ub9c8\uc9c0\ub9c9\uc73c\ub85c \uac01 \uc704\uce58\uc5d0\uc11c \uc800\uc7a5\ub41c \ucd5c\ub300 \ub192\uc774\uc640 \ud604\uc7ac \ub192\uc774\ub97c \ud1b5\ud574 \uace0\uc778 \ubb3c\uc758 \uc591\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n<\/p>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\uacb0\ub860<\/h2>\n
\ucd94\uac00 \uc5f0\uc2b5 \ubb38\uc81c<\/h2>\n