\n \uc8fc\uc5b4\uc9c4 \uc218\uc5f4\uc5d0\uc11c \ud2b9\uc815\ud55c \uc870\uac74\uc744 \ub9cc\uc871\ud558\ub294 K\ubc88\uc9f8 \uc218\ub97c \uad6c\ud558\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \ub2e4\uc74c\uacfc \uac19\uc740 \uc694\uad6c\uc0ac\ud56d\uc744 \ub9cc\uc871\ud574\uc57c \ud569\ub2c8\ub2e4:\n <\/p>\n
\n 6\n 3\n 2\n 1\n 5\n 4\n 6\n 2 5 3\n 4 4 1\n 1 6 2\n <\/pre>\n\uc608\uc81c \ucd9c\ub825<\/h3>\n
\n 5\n 4\n 2\n <\/pre>\n\ubb38\uc81c \uc811\uadfc \ubc29\uc2dd<\/h2>\n
\n \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e4\uc74c\uc758 \ub2e8\uacc4\ub97c \ubc1f\uc544\uc57c \ud569\ub2c8\ub2e4:\n <\/p>\n
\n
- \uc218\uc5f4\uc758 \ud06c\uae30 N\uc744 \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uc218\uc5f4\uc758 \uc6d0\uc18c\ub4e4\uc744 \ubc30\uc5f4 \ud615\ud0dc\ub85c \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- K\ubc88\uc9f8 \uc218\ub97c \uad6c\ud558\uae30 \uc704\ud574 \ubc18\ubcf5\ubb38\uc744 \ud1b5\ud574 \uc5ec\ub7ec \uc870\uac74\uc744 \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
- \uac01 \uc870\uac74\uc5d0 \ub300\ud574 \ubd80\ubd84 \uc218\uc5f4\uc744 \ubd84\ub9ac\ud558\uace0 \uc815\ub82c \ud6c4 K\ubc88\uc9f8 \uc218\ub97c \ucc3e\uc2b5\ub2c8\ub2e4.<\/li>\n<\/ol>\n
\ubb38\uc81c \ud574\uacb0\uc744 \uc704\ud55c \uc790\ubc14 \ucf54\ub4dc<\/h2>\n
\n\n import java.util.*;\n\n public class KthNumber {\n public static void main(String[] args) {\n Scanner sc = new Scanner(System.in);\n \n \/\/ \uc218\uc5f4\uc758 \ud06c\uae30 N\n int N = sc.nextInt();\n int[] array = new int[N];\n \n \/\/ \uc218\uc5f4 \uc785\ub825 \ubc1b\uae30\n for (int i = 0; i < N; i++) {\n array[i] = sc.nextInt();\n }\n \n \/\/ K\ubc88\uc9f8 \uc218\ub97c \uad6c\ud560 \ucffc\ub9ac \uc218 Q\n int Q = sc.nextInt();\n \n \/\/ \ucffc\ub9ac \ucc98\ub9ac\n for (int q = 0; q < Q; q++) {\n int i = sc.nextInt();\n int j = sc.nextInt();\n int k = sc.nextInt();\n \n \/\/ \ubd80\ubd84 \uc218\uc5f4 \uc0dd\uc131\n int[] subArray = Arrays.copyOfRange(array, i - 1, j);\n Arrays.sort(subArray);\n \n \/\/ K\ubc88\uc9f8 \uc218 \ucd9c\ub825\n System.out.println(subArray[k - 1]);\n }\n sc.close();\n }\n }\n <\/code>\n <\/pre>\n\uc138\ubd80 \uc124\uba85<\/h2>\n
1. \uc785\ub825 \ucc98\ub9ac<\/h3>\n
\n \uc785\ub825\uc758 \uccab \ubc88\uc9f8 \uc904\uc5d0\uc11c \uc218\uc5f4\uc758 \ud06c\uae30 N\uc744 \uc785\ub825\ubc1b\uace0, \ub2e4\uc74c N\uac1c\uc758 \uc218\ub97c \uc785\ub825\ubc1b\uc544 \ubc30\uc5f4\uc5d0 \uc800\uc7a5\ud569\ub2c8\ub2e4.
\n \uc774 \ud6c4 K\ubc88\uc9f8 \uc218\uc5d0 \ub300\ud55c \ucffc\ub9ac \uc218 Q\ub97c \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.\n <\/p>\n2. \ucffc\ub9ac \ucc98\ub9ac<\/h3>\n
\n \ubc18\ubcf5\ubb38\uc744 \ud1b5\ud574 \uac01 \ucffc\ub9ac\uc5d0\uc11c i, j, k \uac12\uc744 \uc785\ub825\ubc1b\uace0, \ud574\ub2f9\ud558\ub294 \ubd80\ubd84 \uc218\uc5f4\uc744 \ub9cc\ub4ed\ub2c8\ub2e4.
\nArrays.copyOfRange()<\/code> \uba54\uc18c\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc218\uc5f4\uc758 i\ubc88\uc9f8\ubd80\ud130 j\ubc88\uc9f8\uae4c\uc9c0\uc758 \ubc94\uc704\ub97c \uc798\ub77c\ub0b4\uc5b4 \uc0c8\ub85c\uc6b4 \ubc30\uc5f4subArray<\/code>\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4.\n <\/p>\n3. \ubd80\ubd84 \uc218\uc5f4 \uc815\ub82c<\/h3>\n
\n
Arrays.sort()<\/code> \uba54\uc18c\ub4dc\ub97c \uc0ac\uc6a9\ud558\uc5ec \uc0dd\uc131\ub41c \ubd80\ubd84 \uc218\uc5f4\uc744 \uc815\ub82c\ud569\ub2c8\ub2e4.
\n \uc774\ud6c4 K\ubc88\uc9f8 \uc218\ub294 \uc815\ub82c\ub41c \ubc30\uc5f4\uc758 K-1 \uc778\ub371\uc2a4\uc5d0 \ud574\ub2f9\ud558\ub294 \uac12\uc744 \uc758\ubbf8\ud558\uac8c \ub429\ub2c8\ub2e4.\n <\/p>\n4. \uacb0\uacfc \ucd9c\ub825<\/h3>\n
\n \uac01 \ucffc\ub9ac\ub9c8\ub2e4 K\ubc88\uc9f8 \uc218\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.
\n \uc774 \uacfc\uc815\uc774 \ubc18\ubcf5\ub418\uc5b4 \ubaa8\ub4e0 \ucffc\ub9ac\uac00 \ucc98\ub9ac\ub420 \ub54c\uae4c\uc9c0 \uc9c4\ud589\ub429\ub2c8\ub2e4.\n <\/p>\n\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n \uc774 \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 \ub2e4\uc74c\uacfc \uac19\uc774 \ubd84\uc11d\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n
\n
- \uc218\uc5f4\uc758 \ud06c\uae30 N\uc744 \uc785\ub825\ubc1b\ub294 \uacfc\uc815\uc740 O(N)\uc785\ub2c8\ub2e4.<\/li>\n
- \uac01 \ucffc\ub9ac\ub9c8\ub2e4 \ubd80\ubd84 \uc218\uc5f4\uc744 \ub9cc\ub4dc\ub294 \ub370 O(j – i + 1) \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4.<\/li>\n
- \ubd80\ubd84 \uc218\uc5f4\uc744 \uc815\ub82c\ud558\ub294 \ub370 O((j – i + 1) log(j – i + 1)) \uc2dc\uac04\uc774 \ud544\uc694\ud569\ub2c8\ub2e4.<\/li>\n
- \ub530\ub77c\uc11c \uc804\uccb4 \ucffc\ub9ac\ub97c \ucc98\ub9ac\ud558\ub294 \ub370 \ud3c9\uade0\uc801\uc73c\ub85c O(Q * (j-i+1) log(j-i+1))\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4.<\/li>\n<\/ul>\n
\uacb0\ub860<\/h2>\n
\n \u201cK\ubc88\uc9f8 \uc218 \uad6c\ud558\uae30\u201d \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998\uc758 \uae30\ucd08\uc801\uc778 \uac1c\ub150\uc744 \uc775\ud788\uae30\uc5d0 \uc801\ud569\ud55c \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \ubc30\uc5f4\uacfc \uc815\ub82c\uc758 \uae30\ubcf8\uc801\uc778 \uc0ac\uc6a9\ubc95\uc744 \uace0\ucc30\ud560 \uc218 \uc788\uc73c\uba70, \uc790\ubc14\uc5d0\uc11c \uc81c\uacf5\ud558\ub294 \ub77c\uc774\ube0c\ub7ec\ub9ac\ub97c \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ucf54\ub529\ud14c\uc2a4\ud2b8\uc5d0\uc11c \ube48\ubc88\ud558\uac8c \uc811\ud560 \uc218 \uc788\ub294 \ubb38\uc81c \uc720\ud615\uc774\ub77c \ubc18\ub4dc\uc2dc \uc5f0\uc2b5\ud574\ub450\uc5b4\uc57c \ud560 \uac83\uc785\ub2c8\ub2e4.\n <\/p>\n<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"