ch6_정렬.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "ch6_정렬.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyPpFiFWWe2wVLDeDn7XWgCA",
      "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/babeebird/ThisCodingTest/blob/main/ch6_%EC%A0%95%EB%A0%AC.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 정렬 Sorting\n",
        "- 한 마디로 말하자면\n",
        "  - 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 \n",
        "\n",
        "- 좀 더 자세히 말하자면\n",
        "  - 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에, 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용됨 \n",
        "  - 정렬 알고리즘은 이진 탐색(Binaray Search)의 전처리 과정이기도 하다! \n",
        "  - 다양한 정렬 알고리즘 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해 알아보자\n",
        "  - \"알고리즘의 효율성\"을 이해해보자.\n",
        "  - 면접에서 단골 문제로 출제된다!  \n",
        "  - 선택정렬, 삽입정렬, 퀵정렬은 비교정렬에 해당\n",
        "  \n",
        "#### 선택 정렬\n",
        "- 한 마디로 말하자면\n",
        "  - 선택정렬(Selection Sort)은 \"매번 가장 작은 것을 선택한다\" \n",
        "\n",
        "- 좀 더 자세히 말하자면\n",
        "  - 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복한다. \n",
        "  - 원시적인 방법\n"
      ],
      "metadata": {
        "id": "536N0h8KQL7s"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "HAeQUVmFP9Oi",
        "outputId": "f7c3c136-01a8-4ddc-b130-a73944b70957"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "CPU times: user 2 µs, sys: 1 µs, total: 3 µs\n",
            "Wall time: 5.48 µs\n"
          ]
        }
      ],
      "source": [
        "%%time\n",
        "\n",
        "#- 예제 6-1. 선택 정렬\n",
        "'''\n",
        "- 선택 정렬의 시간 복잡도는 O(N^2)\n",
        "선택 정렬은 N-1 만큼 가장 작은 수를 찾아 맨 앞으로 보내는 것. \n",
        "매번 가장 작은 수를 찾기 위해 비교 연산이 필요.\n",
        "만약 정렬해야 할 데이터 개수가 100배 늘어나면, 이론적으로 수행 시간으 10,000배로 늘어남.\n",
        "\n",
        "- 문제 정리\n",
        "1. N=10 개의 데이터를 선택정렬을 이용해서 오름차순으로 정렬하여 출력한다. \n",
        "\n",
        "- 자연어 알고리즘\n",
        "0. 선택정렬을 수행하는 select_sort를 정의한다. \n",
        "   이때, 배열 array를 인자로 입력 받는다. \n",
        "2. for문 - range(array의 요소 개수) 만큼 반복하여 i에 할당한다.\n",
        "   2-1. min_index 는 i로 초기화한다. \n",
        "   2-2. for문 - range(i+1에서 array의 요소개수까지) 반복하여 j에 할당한다. \n",
        "    2-2-1. 조건문 - 만약 array[min_index]가 array[j]보다 크면 \n",
        "      min_index를 j로 갱신한다. \n",
        "  \n",
        "    2-3.array[i]와 array[min_index]를 스와프 한다. \n",
        "    스와프란 특정 리스트가 주어졌을 때, 두 변수의 위치를 변경하는 작업 \n",
        "'''\n",
        "\n",
        "array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "def select_sort(array):\n",
        "  for i in range(len(array)):\n",
        "      min_index = i # 가장 작은 원소의 인덱스\n",
        "      for j in range(i + 1, len(array)):\n",
        "          if array[min_index] > array[j]:\n",
        "              min_index = j\n",
        "      array[i], array[min_index] = array[min_index], array[i] # 스와프Swap\n",
        "      \n",
        "\n",
        "  print(array)\n",
        "  "
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# 0 인덱스와 1 인덱스의 원소 교체하기\n",
        "array = [3, 5]\n",
        "array[0], array[1] = array[1], array[0]\n",
        "\n",
        "print(array)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "bL3alQOvk-nh",
        "outputId": "04b4e7ed-b4db-4f05-a1af-c3867806eead"
      },
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[5, 3]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 삽입 정렬 Insertion Sort\n",
        "- 한 마디로 말하자면\n",
        "  - 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하자 \n",
        "- 좀 더 자세히 말하자면\n",
        "  - 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높지만, 선택 정렬에 비해 실행 시간 측면에서 더 효율적임.\n",
        "  - 삽입 정렬은 필요할 때만 윌치를 바꾸므로, 데이터가 거의 정렬 되어있을 때 훨씬 효율적임.\n",
        "  - 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정함. \n",
        "\n"
      ],
      "metadata": {
        "id": "kDsF9omSbcuc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "\n",
        "#- 예제 6-3. 삽입 정렬\n",
        "'''\n",
        "- 삽입 정렬의 시간 복잡도는 O(N^2)\n",
        "선택정렬과 마찬가지로 반복문이 2번 중첩됨\n",
        "수행시간은 선택 정렬과 흡사한 시간이 소요됨\n",
        "삽입정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작! 최선의 경우 O(N)의 시간 복잡도.\n",
        "'''\n",
        "array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "for i in range(1, len(array)):\n",
        "    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법\n",
        "        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동\n",
        "            array[j], array[j - 1] = array[j - 1], array[j]\n",
        "        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤\n",
        "            break\n",
        "\n",
        "print(array)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-X7t9fYKlGpv",
        "outputId": "bdbf1d24-808f-49f9-981f-13afac6a95f2"
      },
      "execution_count": 3,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
            "CPU times: user 913 µs, sys: 0 ns, total: 913 µs\n",
            "Wall time: 2.49 ms\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 퀵 정렬 (빠른 정렬 알고리즘)\n",
        "- 한 마디로 말하자면\n",
        "  - 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔보자.\n",
        "- 좀 더 자세히 말하자면\n",
        "  - 분할 정복 알고리즘 - 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음에 결과를 모아서 원래의 문제를 해결 \n",
        "  - 퀵 정렬에서는 pivot이 사용됨. \n",
        "  - 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 기준을 피벗이라 표현 \n",
        "  - 퀵 정렬을 수행하기 전에 피벗을 어떻게 설정할 것인지 미리 명시해야 함.\n",
        "  - 피벗 설정과 리스트 분할하는 방법은 여러가지인데, 여기서는 대표적인 분할 방식인 호어분할(Hoare Partition) 방식을 기준으로 보자.\n",
        "  - 호어분할은 \"리스트에서 첫 번쨰 데이터를 피벗으로 정한다\" \n",
        "  - 이같이 피벗을 설정한 후에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. \n",
        "  - 그다음으로 큰 데이터와 작은 데이터의 위치를 서로 교환한다.\n",
        "  - 이 과정을 반복하면 피벗에 대해 정렬이 수행됨.\n",
        "  - 이미 데이터가 정렬되어 있는 경우, 매우 느리게 동작\n",
        "  \n",
        "- 과정 설명 \n",
        "  1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.\n",
        "  2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)\n",
        "피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.\n",
        "    - 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.\n",
        "    - 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.\n",
        "  3. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.\n",
        "    - 리스트의 크기가 0이나 1이 될 때까지 반복한다.\n",
        "  "
      ],
      "metadata": {
        "id": "5Oq92upYytjC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "\n",
        "#- 예제 6-4. 퀵 정렬 (정통)\n",
        "\n",
        "array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "def quick_sort(array, start, end):\n",
        "    if start >= end: # 원소가 1개인 경우 종료\n",
        "        return\n",
        "    pivot = start # 피벗은 첫 번째 원소\n",
        "    left = start + 1\n",
        "    right = end\n",
        "    while(left <= right):\n",
        "        # 피벗보다 큰 데이터를 찾을 때까지 반복 \n",
        "        while(left <= end and array[left] <= array[pivot]):\n",
        "            left += 1\n",
        "        # 피벗보다 작은 데이터를 찾을 때까지 반복\n",
        "        while(right > start and array[right] >= array[pivot]):\n",
        "            right -= 1\n",
        "        if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체\n",
        "            array[right], array[pivot] = array[pivot], array[right]\n",
        "        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체\n",
        "            array[left], array[right] = array[right], array[left]\n",
        "    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행\n",
        "    quick_sort(array, start, right - 1)\n",
        "    quick_sort(array, right + 1, end)\n",
        "\n",
        "quick_sort(array, 0, len(array) - 1)\n",
        "print(array)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "taXPE3WUlHFt",
        "outputId": "414a0846-c669-429e-ad93-a0178a7d1e06"
      },
      "execution_count": 4,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
            "CPU times: user 419 µs, sys: 0 ns, total: 419 µs\n",
            "Wall time: 424 µs\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 6-5. 퀵 정렬 (파이썬)\n",
        "#- 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로 시간 면에서 조금 비효율적임. \n",
        "#- 직관적이고 기억하기 쉽다는 장점이 있음! \n",
        "'''\n",
        "- 시간 복잡도는 O(NlogN)\n",
        "'''\n",
        "\n",
        "array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "def quick_sort(array):\n",
        "    # 리스트가 하나 이하의 원소만을 담고 있다면 종료\n",
        "    if len(array) <= 1:\n",
        "        return array\n",
        "\n",
        "    pivot = array[0] # 피벗은 첫 번째 원소\n",
        "    tail = array[1:] # 피벗을 제외한 리스트\n",
        "\n",
        "    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분\n",
        "    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분\n",
        "\n",
        "    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환\n",
        "    return quick_sort(left_side) + [pivot] + quick_sort(right_side)\n",
        "\n",
        "print(quick_sort(array))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "4imRBZBplPQV",
        "outputId": "ab9f7dc1-6514-425a-ad15-572f814905f0"
      },
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "#### 계수 정렬 Count Sort\n",
        "- 한 마디로 말하자면\n",
        "  \n",
        "- 좀 더 자세히 말하자면  \n",
        "  - 특정한 조건이 부합할 때만 사용할 수 있지만 매울 빠른 정렬 알고리즘\n",
        "  - 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있음. \n",
        "  - 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. \n",
        "  - 모든 범위를 담을 수 있는 크기의 리스트를 선언해야 함. \n",
        "  - 비교기반의 정렬 알고리즘이 아님.\n",
        "  - 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있음.\n",
        "  - 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 유리함.\n"
      ],
      "metadata": {
        "id": "-ImTLNLcCEjd"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "#- 예제 6-6. 계수 정렬\n",
        "'''\n",
        "시간복잡도는 O(N+K) - 데이터의 개수가 N, 데이터 중 최대값의 크기가 K일때\n",
        "'''\n",
        "\n",
        "# 모든 원소의 값이 0보다 크거나 같다고 가정\n",
        "array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]\n",
        "# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)\n",
        "count = [0] * (max(array) + 1)\n",
        "\n",
        "for i in range(len(array)):\n",
        "    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가\n",
        "\n",
        "for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인\n",
        "    for j in range(count[i]):\n",
        "        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "RkBHDnNllTe3",
        "outputId": "ccabcde7-ddd6-4282-cf98-05e4b1778f4e"
      },
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0 0 1 1 2 2 3 4 5 5 6 7 8 9 9 "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 6-7. sorted() 파이썬 기본 정렬 라이브러리 \n",
        "#- sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어짐. \n",
        "#- 리스트 자료형 반환\n",
        "\n",
        "array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "result = sorted(array)\n",
        "print(result)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WFm91n4clZP0",
        "outputId": "04097842-060c-4cf6-bcd4-2fd19c6049fb"
      },
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 6-8. sort() 리스트 객체의 내장 함수\n",
        "#- 내부 원소가 정렬됨 \n",
        "\n",
        "array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]\n",
        "\n",
        "array.sort()\n",
        "print(array)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-bnK5HjLFkgg",
        "outputId": "e8e7e62c-51bb-4959-c6ac-690f9ade126f"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 6-9. 정렬 라이브러리에서 key를 활용\n",
        "#- sorted() 나 sort()를 이용할 때, key 매개변수를 입력으로 받을 수 있음. \n",
        "#- key 값으로는 하나의 함수가 들어가야 하며, 이는 정렬 기준이 됨. \n",
        "\n",
        "array = [('바나나', 2), ('사과', 5), ('당근', 3)]\n",
        "\n",
        "def setting(data):\n",
        "    return data[1]\n",
        "\n",
        "# result = sorted(array, key=setting)\n",
        "result = sorted(array, key = lambda x: x[1])\n",
        "print(result)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "NippUaGelbq2",
        "outputId": "887b1261-0b21-4f0d-af5a-0c119b38306a"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[('바나나', 2), ('당근', 3), ('사과', 5)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "#- 실전문제 2. 위에서 아래로 \n",
        "'''\n",
        "- 문제정의\n",
        "1. 첫째 줄에 수열에 속해 있는 수의 개수 N이 주어진다 (1<=N<=50)\n",
        "2. 둘째 줄부터 N+1 번째 줄까지 N개의 수가 입력된다. 수의 범위는 1이상 100,000이하의 자연수이다.\n",
        "3. 입력으로 주어진 수열이 내림차순으로 정렬된 결과를 공백으로 구분하여 출력.\n",
        "   이때, 동일한 수의 순서는 자유롭게 출력!\n",
        "\n",
        "- 자연어 알고리즘\n",
        "1. 배열의 크기를 변수 n에 입력받는다. (int type 변환)\n",
        "2. 요소를 저장할 빈 리스트 array 변수를 생성\n",
        "3. for 문 - range(n) 반복하여 변수 i에 할당 \n",
        "  - 배열의 요소를 n번 입력받아 int 타입으로 변환한 후, 변수 array의 끝에 추가함 \n",
        "4. sorted 함수를 활용해서 내림차순 정렬 수행 \n",
        "5. for문 - array의 요소를 꺼내어 i에 할당 \n",
        "  - i를 공백 기준으로 출력 \n",
        "\n",
        "'''\n",
        "\n",
        "# N 입력 받기\n",
        "n = int(input())\n",
        "\n",
        "# N개의 정수를 입력 받아 리스트에 저장\n",
        "array = []\n",
        "for i in range(n):\n",
        "    array.append(int(input()))\n",
        "\n",
        "# 파이썬 정렬 라이브러리를 이용하여 내림차순 정렬 수행\n",
        "array = sorted(array, reverse=True) \n",
        "\n",
        "# 정렬이 수행된 결과를 출력\n",
        "for i in array:\n",
        "    print(i, end=' ')"
      ],
      "metadata": {
        "id": "3mTDEDSvlcEs",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "52615a84-3032-4300-d65f-8a56dd21585b"
      },
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "15\n",
            "27\n",
            "12\n",
            "27 15 12 CPU times: user 84.1 ms, sys: 16.4 ms, total: 101 ms\n",
            "Wall time: 17.2 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "%%time\n",
        "n = int(input())\n",
        "array = [int(input()) for _ in range(n)]\n",
        "\n",
        "array.sort(reverse=True)\n",
        "print(array)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FuRIIRgFxlWc",
        "outputId": "1cb5eb0a-f093-4bad-e6a5-a9bd10012542"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "27\n",
            "15\n",
            "12\n",
            "[27, 15, 12]\n",
            "CPU times: user 30.8 ms, sys: 6.91 ms, total: 37.7 ms\n",
            "Wall time: 6.99 s\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 실전문제 3. 성적이 낮은 순서로 학생 출력하기\n",
        "\n",
        "'''\n",
        "- 문제정의\n",
        "1. 첫 번째 줄에 학생의 수 N이 입력됨 (1<=N<=100,000)\n",
        "2. 두 번째 줄부터 N+1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력\n",
        "   이때, 문자열 A의 길이와 학생의 성적은 100 이하의 자연수임. \n",
        "3. 모든 학생의 이름을 성적이 낮은 순서대로 출력. 성적이 동일한 학생들의 순서는 자유롭게 출력! \n",
        "\n",
        "- 자연어 알고리즘\n",
        "1. 배열의 크기를 변수 n에 입력받는다. (int type 변환)\n",
        "2. 요소를 저장할 빈 리스트 array 변수를 생성\n",
        "3. for 문 - range(n) 반복하여 변수 i에 할당 \n",
        "  - 배열의 요소를 n번 입력(이름과 점수가 공백기준으로 입력됨) 받아 split()을 하여 input data 변수에 저장\n",
        "  - 변수 array에 (이름, 점수)를 튜플로 저장. 이때 점수만 int type으로 변환\n",
        "4. sorted 함수에서 array를 오름차순으로 정렬하는데, 학생의 점수를 기준으로 정렬하여 array에 재할당\n",
        "5. for문 - array의 요소를 student에 할당 \n",
        "  - student[0] 요소인 이름을 공백기준으로 출력\n",
        "'''\n",
        "\n",
        "# N 입력 받기\n",
        "n = int(input())\n",
        "\n",
        "# N명의 학생 정보를 입력 받아 리스트에 저장\n",
        "array = []\n",
        "for i in range(n):\n",
        "    input_data = input().split()\n",
        "    # 이름은 문자열 그대로, 점수는 정수형으로 변환하여 저장\n",
        "    array.append((input_data[0], int(input_data[1])))\n",
        "\n",
        "# 키(Key)를 이용하여, 점수를 기준으로 정렬\n",
        "array = sorted(array, key=lambda student: student[1])\n",
        "\n",
        "# 정렬이 수행된 결과를 출력\n",
        "for student in array:\n",
        "    print(student[0], end=' ')"
      ],
      "metadata": {
        "id": "pTgTGuWhlfWC",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "9eb6254b-3ab1-432a-e061-115dd0482589"
      },
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n",
            "김땡땡 90\n",
            "이땡땡 25\n",
            "박땡땡 67\n",
            "이땡땡 박땡땡 김땡땡 "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#- 실전문제 4. 두 배열의 원소 교체 \n",
        "\n",
        "'''\n",
        "- 문제정의\n",
        "1. 첫 번째 줄에 N,K가 공백으로 구분되어 입력됨 (1<=N<=100,000, 0<=K<=N)\n",
        "2. 두번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력됨. 모든 원소는 10,000,000보다 작은 자연수\n",
        "3. 세번쨰 줄에 배열 B의 원소들이 공백으로 구분되어 입력됨. 모든 원소는 10,000,000보다 작은 자연수\n",
        "4. 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력.\n",
        "\n",
        "- 자연어 알고리즘\n",
        "1. 배열의 크기와 바꿔치기 횟수를 각각 N, K로 입력받는다. int type으로 변환\n",
        "2. 변수 a 배열의 원소를 공백 기준으로 입력 받아서 int type으로 변환\n",
        "3. 변수 b 배열의 원소를 공백 기준으로 입력 받아서 int type으로 변환\n",
        "4. 변수 a는 오름차순 정렬할때 a.sort()를 활용 \n",
        "5. 변수 b는 내림차순 정렬할때 b.sort(reverse=True)\n",
        "6. for 문 - K번 반복하여 i에 할당 \n",
        "  - if 조건문 : a[i]와 b[i]를 비교하여 b[i]가 더 큰 경우\n",
        "    - swap \n",
        "  - 아니면 \n",
        "    - break\n",
        "7. print(sum(a))\n",
        "'''\n",
        "n, k = map(int, input().split()) # N과 K를 입력 받기\n",
        "a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기\n",
        "b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기\n",
        "\n",
        "a.sort() # 배열 A는 오름차순 정렬 수행\n",
        "b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행\n",
        "\n",
        "# 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교\n",
        "for i in range(k):\n",
        "    # A의 원소가 B의 원소보다 작은 경우\n",
        "    if a[i] < b[i]:\n",
        "        # 두 원소를 교체\n",
        "        a[i], b[i] = b[i], a[i]\n",
        "    else: # A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출\n",
        "        break\n",
        "\n",
        "print(sum(a)) # 배열 A의 모든 원소의 합을 출력"
      ],
      "metadata": {
        "id": "XCs7URhBliGZ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "71057ca8-2e49-4270-a5b5-38f4f836f237"
      },
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "5 3\n",
            "1 2 5 4 3\n",
            "5 5 6 6 5\n",
            "26\n"
          ]
        }
      ]
    }
  ]
}