algorithm/List/dynamic_array_increasing_subsequences.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [문제]  \n",
    "\n",
    "주어진 리스트의 nums의 인덱스 i, j, k에 대해  \n",
    "**`i < j < k` 이며  `nums[i] < nums[j] < nums[k]`가 존재하면 true**  \n",
    "그렇지 않으면 false를 return 해라.  \n",
    "  \n",
    "단, 시간복잡도는 O(n), 공간복잡도는  O(1)으로 풀이해라.  \n",
    "  \n",
    "link: https://leetcode.com/problems/increasing-triplet-subsequence/description  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### [풀이]\n",
    "- `first` : 지금까지 나온 원소(`num[i]`) 중 가장 작은 원소\n",
    "- `second` : `i < j, nums[i] < nums[j]` 를 만족하는 가장 작은 `nums[j]`\n",
    "- `second`보다 큰 원소가 나오면 `i < j < k, nums[i] < nums[j] < nums[k]` 를 만족하는 k를 찾는 것이므로 True를 반환하고, 리스트 끝까지 조건을 만족하지 못하면 False를 반환한다. \n",
    "\n",
    "#### [예시]\n",
    "nums = [3, 5, 2, 0, 7]  \n",
    "\n",
    "i = 0일 때, nums[0]=3 -> 지금까지 수 중 가장 작음  \n",
    "**first = 3**  \n",
    "\n",
    "i = 1일 때, nums[1]=5 -> first(3) < 5 만족함  \n",
    "first = 3  \n",
    "**second = 5**  \n",
    "  \n",
    "i = 2일때, nums[2]=2 -> 지금까지 수 중 가장 작음  \n",
    "**first = 2**  \n",
    "second = 5  \n",
    "  \n",
    "i = 3일 때, nums[3]=0 -> 지금까지 수 중 가장 작음  \n",
    "**first = 0**  \n",
    "second = 5  \n",
    "  \n",
    "i=4일 때, nums[4]=7 -> second(5) < 7 만족함  \n",
    "**True**  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m'/usr/local/bin/python3.11'(으)로 셀을 실행하려면 ipykernel 패키지가 필요합니다.\n",
      "\u001b[1;31mRun the following command to install 'ipykernel' into the Python environment. \n",
      "\u001b[1;31mCommand: '/usr/local/bin/python3.11 -m pip install ipykernel -U --user --force-reinstall'"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def increasingTriplet(self, nums):\n",
    "        first = second = float('inf')\n",
    "        for n in nums:\n",
    "            if n <= first:\n",
    "                first = n\n",
    "            elif n <= second:\n",
    "                second = n\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}