\n \uc8fc\uc5b4\uc9c4 \uc218 N\uac1c\ub97c \ube44\ub0b4\ub9bc\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624. \ube44\ub0b4\ub9bc\ucc28\uc21c\uc740 \uc815\ub82c\ub41c \uc21c\uc11c\uc5d0\uc11c \uc774\uc804 \uc22b\uc790\ubcf4\ub2e4 \uac19\uc740 \uc22b\uc790\uc774\uac70\ub098 \ud070 \uc22b\uc790\uac00 \ub098\uc624\ub294 \uacbd\uc6b0\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.\n <\/p>\n
\n \uccab\uc9f8 \uc904\uc5d0 \uc218\uc758 \uac1c\uc218 N (1 \u2264 N \u2264 1,000,000)\uc774 \uc8fc\uc5b4\uc9c4\ub2e4. \ub458\uc9f8 \uc904\ubd80\ud130 N\uac1c\uc758 \uc904\uc5d0 \uc218\uac00 \uc8fc\uc5b4\uc9c4\ub2e4. \uac01 \uc218\ub294 \uc815\uc218\uc774\uace0, \uc808\ub313\uac12\uc774 1,000,000\ubcf4\ub2e4 \uc791\uac70\ub098 \uac19\ub2e4.\n <\/p>\n
\n \uccab\uc9f8 \uc904\ubd80\ud130 N\uac1c\uc758 \uc904\uc5d0 \uc624\ub984\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ub41c \uc218\ub97c \ud558\ub098\uc529 \ucd9c\ub825\ud55c\ub2e4.\n <\/p>\n
\ucd9c\ub825 \uc608\uc2dc:<\/strong> \n \uc8fc\uc5b4\uc9c4 \ubb38\uc81c\ub97c \uc774\ud574\ud558\uae30 \uc704\ud574 \uc785\ub825 \ub370\uc774\ud130\uc758 \uad6c\uc870\uc640 \uc694\uad6c\ub418\ub294 \ucd9c\ub825\uc744 \ubd84\uba85\ud788 \ud574\uc57c \ud569\ub2c8\ub2e4. \n \ubb38\uc81c\uc758 \ud575\uc2ec\uc740 \ud6a8\uc728\uc801\uc778 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \n \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\uc758 \ub0b4\uc7a5 \uba54\uc18c\ub4dc\uc778 \n \ubcd1\ud569 \uc815\ub82c(Merge Sort) \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uaca0\uc2b5\ub2c8\ub2e4. \n \uc774\uc81c \uc785\ub825\uc744 \ubc1b\uace0 \ubcd1\ud569 \uc815\ub82c\uc744 \uc774\uc6a9\ud558\uc5ec \uc815\ub82c\ud55c \ud6c4, \uacb0\uacfc\ub97c \ucd9c\ub825\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4. \n \uad6c\ud604\ub41c \ucf54\ub4dc\ub97c \ud14c\uc2a4\ud2b8\ud558\uace0, \uc785\ub825 \uc608\uc81c\ub97c \uc0ac\uc6a9\ud558\uc600\uc2b5\ub2c8\ub2e4. \n \uc608\uc0c1\ub418\ub294 \ucd9c\ub825\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc774\ubc88 \ubb38\uc81c\ub97c \ud1b5\ud574 \uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8\ub97c \ud65c\uc6a9\ud55c \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc758 \uc911\uc694\uc131\uacfc \ubcd1\ud569 \uc815\ub82c\uc758 \uad6c\ud604 \ubc29\ubc95\uc744 \ubc30\uc6b8 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4.
\n 1
\n 2
\n 3
\n 4
\n 5\n <\/div>\n\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \ubb38\uc81c \ubd84\uc11d<\/h3>\n
\n – \uc785\ub825: \uc218 N\uacfc \uadf8 \ub2e4\uc74c N\uac1c\uc758 \uc815\uc218
\n – \ucd9c\ub825: N\uac1c\uc758 \uc815\uc218\ub97c \ube44\ub0b4\ub9bc\ucc28\uc21c\uc73c\ub85c \uc815\ub82c\ud55c \uacb0\uacfc\n <\/p>\n
\n \ubc30\uc5f4\uc758 \ud06c\uae30\uac00 \ucd5c\ub300 1,000,000\uc774\uae30 \ub54c\ubb38\uc5d0 \uc77c\ubc18\uc801\uc778 O(N^2) \uc54c\uace0\ub9ac\uc998(\ubc84\ube14 \uc815\ub82c, \uc120\ud0dd \uc815\ub82c \ub4f1)\uc740 \uc0ac\uc6a9\ud560 \uc218 \uc5c6\uc2b5\ub2c8\ub2e4.
\n \uadf8\ub7ec\ubbc0\ub85c O(N log N)\uc758 \ubcf5\uc7a1\ub3c4\ub97c \uac16\ub294 \uc815\ub82c \uc54c\uace0\ub9ac\uc998\uc778 \ud035 \uc815\ub82c, \ubcd1\ud569 \uc815\ub82c \ub4f1\uc744 \uc0ac\uc6a9\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n2\ub2e8\uacc4: \uc54c\uace0\ub9ac\uc998 \uc120\ud0dd<\/h3>\n
Array.prototype.sort()<\/code>\ub97c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc9c0\ub9cc,
\n \uc815\ub82c\uc758 \uc548\uc815\uc131\uc744 \ubcf4\uc7a5\ud574\uc57c \ud558\uae30 \ub54c\ubb38\uc5d0 \ucffc\ud0a4 \uc815\ub82c\uc774\ub098 \ubcd1\ud569 \uc815\ub82c\uc744 \uad6c\ud604\ud574 \ubcfc \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n3\ub2e8\uacc4: \uad6c\ud604<\/h3>\n
\n \ubcd1\ud569 \uc815\ub82c\uc740 \ub9ac\uc2a4\ud2b8\ub97c \ubc18\uc73c\ub85c \ub098\ub204\uace0, \uac01 \ubd80\ubd84\uc744 \uc7ac\uadc0\uc801\uc73c\ub85c \uc815\ub82c\ud55c \ud6c4, \ub450 \uc815\ub82c\ub41c \ubd80\ubd84\uc744 \ud569\uce58\ub294 \ubc29\uc2dd\uc73c\ub85c \ub3d9\uc791\ud569\ub2c8\ub2e4.\n <\/p>\n\ubcd1\ud569 \uc815\ub82c\uc758 \uc2e4\ud589 \uacfc\uc815<\/h4>\n
\n
\ubcd1\ud569 \uc815\ub82c \uad6c\ud604<\/h4>\n
\nfunction mergeSort(arr) {\n if (arr.length <= 1) {\n return arr;\n }\n\n const mid = Math.floor(arr.length \/ 2);\n const left = mergeSort(arr.slice(0, mid));\n const right = mergeSort(arr.slice(mid));\n\n return merge(left, right);\n}\n\nfunction merge(left, right) {\n const result = [];\n let i = 0; \n let j = 0;\n\n while (i < left.length && j < right.length) {\n if (left[i] < right[j]) {\n result.push(left[i]);\n i++;\n } else {\n result.push(right[j]);\n j++;\n }\n }\n\n return result.concat(left.slice(i)).concat(right.slice(j));\n}\n <\/code><\/pre>\n4\ub2e8\uacc4: \uc785\ub825 \ubc0f \ucd9c\ub825 \ucc98\ub9ac<\/h3>\n
\n \ub178\ub4dc\ub97c \uc785\ub825\ubc1b\uace0 \ubc30\uc5f4\ub85c \ubcc0\ud658\ud55c \ud6c4 \ubcd1\ud569 \uc815\ub82c \ud568\uc218\ub97c \ud638\ucd9c\ud558\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n\nconst fs = require('fs');\n\n\/\/ \uc785\ub825\uc744 \ud30c\uc77c\uc5d0\uc11c \uc77d\uc2b5\ub2c8\ub2e4.\nlet input = fs.readFileSync('\/dev\/stdin').toString().trim().split('\\n').map(Number);\nconst n = input.shift(); \/\/ \uccab \ubc88\uc9f8 \uc904\uc758 \uc218 \uac1c\uc218\ub97c \uc81c\uac70\ud569\ub2c8\ub2e4.\n\nconst sortedArray = mergeSort(input);\n\nconsole.log(sortedArray.join('\\\\n')); \/\/ \uc904 \ubc14\uafc8\uc73c\ub85c \uc815\ub82c\ub41c \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n <\/code><\/pre>\n5\ub2e8\uacc4: \ud14c\uc2a4\ud2b8 \ubc0f \uacb0\uacfc \uac80\uc99d<\/h3>\n
\n \uc785\ub825\uc73c\ub85c \ub2e4\uc74c\uc744 \uc0ac\uc6a9\ud588\uc744 \ub54c,\n <\/p>\n\n5\n5\n2\n3\n1\n4\n <\/code><\/pre>\n\n1\n2\n3\n4\n5\n <\/code><\/pre>\n\uacb0\ub860<\/h2>\n
\n \uc2e4\uc804 \uba74\uc811 \ubc0f \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \uc8fc\uc81c\uc778 \ub9cc\ud07c, \ub2e4\uc591\ud55c \ucf00\uc774\uc2a4\ub97c \uc5f0\uc2b5\ud558\uace0 \uad6c\ud604\ud574 \ubcf4\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4.
\n \uc54c\uace0\ub9ac\uc998\uc758 \uc774\ub860\uc744 \uc774\ud574\ud558\ub294 \uac83\uacfc \ud568\uaed8, \uc9c1\uc811 \ucf54\ub4dc\ub97c \uc791\uc131\ud574 \ubcf4\uba74\uc11c \uc190\uc5d0 \uc775\ud788\ub294 \uac83\uc774 \uc2e4\ub825\uc744 \ud5a5\uc0c1\uc2dc\ud0a4\ub294 \uc911\uc694\ud55c \ubc29\ubc95\uc785\ub2c8\ub2e4.\n <\/p>\n