\uc774 \ubb38\uc81c\ub294 N\uac1c\uc758 \uc218\uac00 \uc8fc\uc5b4\uc9c8 \ub54c, \uc774\ub4e4\uc744 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\ub294 \uc54c\uace0\ub9ac\uc998\uc744 \uc791\uc131\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc8fc\uc5b4\uc9c4 \uc218\uc758 \ubc94\uc704\ub294 1\ubd80\ud130 10000\uae4c\uc9c0\uc774\uba70, \uac01 \uc218\ub294 0\ubcf4\ub2e4 \ud06c\uace0 10000 \uc774\ud558\uc758 \uc815\uc218\uc785\ub2c8\ub2e4. \uc774 \uc810\uc744 \uace0\ub824\ud574 \ud6a8\uc728\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc8fc\uc5b4\uc9c4 N\uac1c\uc758 \uc218\ub97c \uc815\ub82c\ud558\uc5ec \ud55c \uc904\uc5d0 \ud558\ub098\uc529 \ucd9c\ub825\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc138\uc694. \uc218\uc758 \uac1c\uc218\ub294 \ucd5c\ub300 1,000,000\uac1c\uc77c \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc989, \ub300\ub7c9\uc758 \uc218\ub97c \uc815\ub82c\ud574\uc57c \ud558\ubbc0\ub85c, \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uace0\ub824\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc785\ub825\uc758 \uccab \uc904\uc5d0\ub294 \uc218\uc758 \uac1c\uc218 N(1 \u2264 N \u2264 1,000,000)\uc774 \uc8fc\uc5b4\uc9c0\uace0, \ub2e4\uc74c N\uac1c\uc758 \uc904\uc5d0\ub294 \uac01 \uc218\uac00 \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4.<\/p>\n
\uc815\ub82c\ub41c \uc218\ub97c \ud55c \uc904\uc5d0 \ud558\ub098\uc529 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/p>\n
\n 5\n 5\n 4\n 3\n 2\n 1\n <\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h2>\n
\n 1\n 2\n 3\n 4\n 5\n <\/pre>\n\ubb38\uc81c \ubd84\uc11d<\/h2>\n
Given the constraints, we can use a sorting algorithm that is efficient in terms of time and space. Python’s built-in sorting functionality utilizes Timsort, which has a time complexity of O(N log N) in the average and worst-case scenarios. However, considering the range of numbers is limited (from 1 to 10000), we can also explore counting sort or bucket sort for this specific task.<\/p>\n
\ud574\ubc95 \uc81c\uc2dc<\/h2>\n
\uc6b0\ub9ac\ub294 Counting Sort\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uac83\uc785\ub2c8\ub2e4. Counting Sort\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ubc29\uc2dd\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4:<\/p>\n
\n
- \uc785\ub825\uc73c\ub85c \ubc1b\uc740 \uc218\uc758 \uac1c\uc218\ub97c \uc138\uae30 \uc704\ud574 \uce74\uc6b4\ud305 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \ud06c\uae30\ub294 10001\ub85c \uc124\uc815\ud569\ub2c8\ub2e4 (0~10000 \ud3ec\ud568).<\/li>\n
- \uac01 \uc218\uac00 \ub098\ud0c0\ub098\ub294 \ud69f\uc218\ub97c \uce74\uc6b4\ud305 \ubc30\uc5f4\uc5d0 \uc800\uc7a5\ud569\ub2c8\ub2e4.<\/li>\n
- \uce74\uc6b4\ud305 \ubc30\uc5f4\uc744 \ubc18\ubcf5\ud558\uc5ec \uac01 \uc218\ub97c \uc815\ub82c\ub41c \uc21c\uc11c\ub300\ub85c \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\nimport sys\n\ndef counting_sort(n, numbers):\n count = [0] * 10001 # 0 ~ 10000 \ubc94\uc704\uc758 \uc218\ub97c \uc704\ud574 \ud06c\uae30\ub97c 10001\ub85c \uc0dd\uc131\n\n for num in numbers:\n count[num] += 1 # \uc218\uc758 \uac1c\uc218\ub97c \uce74\uc6b4\ud2b8\n\n result = []\n for i in range(10001):\n while count[i] > 0:\n result.append(i) # count \ubc30\uc5f4\uc758 \uac12\uc744 \uae30\ubc18\uc73c\ub85c \uacb0\uacfc \ubc30\uc5f4\uc5d0 \ucd94\uac00\n count[i] -= 1\n\n return result\n\nif __name__ == \"__main__\":\n n = int(sys.stdin.readline())\n numbers = [int(sys.stdin.readline()) for _ in range(n)]\n \n sorted_numbers = counting_sort(n, numbers)\n print(\"\\n\".join(map(str, sorted_numbers)))\n <\/pre>\n\uc8fc\uc694 \ud3ec\uc778\ud2b8<\/h3>\n
\n
- Counting Sort\ub294 \uc548\uc815\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc785\ub2c8\ub2e4. \uc989, \uac19\uc740 \uac12\uc758 \uc6d0\uc18c\uc758 \uc0c1\ub300\uc801\uc778 \uc704\uce58\uac00 \uc720\uc9c0\ub429\ub2c8\ub2e4.<\/li>\n
- \uc774 \uc54c\uace0\ub9ac\uc998\uc740 O(N + K)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\uba70, \uc5ec\uae30\uc11c N\uc740 \uc785\ub825\uc758 \ud06c\uae30\uc774\uace0 K\ub294 \uc218\uc758 \ubc94\uc704\uc785\ub2c8\ub2e4.<\/li>\n
- \uba54\ubaa8\ub9ac \uc0ac\uc6a9\ub7c9\ub3c4 K\uac00 \ud06c\uc9c0 \uc54a\uc740 \ud55c \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uacb0\ub860<\/h2>\n
\uc774 \ubb38\uc81c\ub97c \ud1b5\ud574 Counting Sort \uc54c\uace0\ub9ac\uc998\uc744 \uc2e4\uc2b5\ud568\uc73c\ub85c\uc368, \uc815\ub82c \uc131\ub2a5\uc744 \uadf9\ub300\ud654\ud558\ub294 \ubc29\ubc95\uc744 \ubc30\uc6b8 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \ub610\ud55c, \ud30c\uc774\uc36c\uc758 \uae30\ubcf8\uc801\uc778 \uc785\ucd9c\ub825 \ucc98\ub9ac\uc640 \ubc30\uc5f4 \uc0ac\uc6a9\ubc95\uc744 \uc775\ud790 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \ub2e4\uc591\ud55c \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ud574\ub294 \ud504\ub85c\uadf8\ub798\ubc0d \uc2dc\ud5d8\uc5d0\uc11c \uc911\uc694\ud55c \uc694\uc18c\uc774\ubbc0\ub85c, \uc774\ub7ec\ud55c \ubc29\uc2dd\uc73c\ub85c \ubb38\uc81c\ub97c \uc811\uadfc\ud558\ub294 \uac83\uc774 \ub9ce\uc740 \ub3c4\uc6c0\uc774 \ub420 \uac83\uc785\ub2c8\ub2e4.<\/p>\n
\ucd94\uac00 \ubb38\uc81c: \ubcc0\ud615 \ubc0f \uc751\uc6a9<\/h2>\n
\ub354 \ub098\uc544\uac00\uc11c, \ub2e4\uc74c\uacfc \uac19\uc740 \ubcc0\ud615 \ubb38\uc81c\ub97c \uc2dc\ub3c4\ud574 \ubcfc \uc218 \uc788\uc2b5\ub2c8\ub2e4:<\/p>\n