\ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc790\uc8fc \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c \uc911 \ud558\ub098\ub294 \ub370\uc774\ud130\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \uc800\uc7a5\ud558\uace0 \uad00\ub9ac\ud558\ub294 \uc790\ub8cc\uad6c\uc870\uc758 \uad6c\ud604\uc785\ub2c8\ub2e4. \ubcf8 \uae00\uc5d0\uc11c\ub294 \uc808\ub313\uac12 \ud799(absmin heap)<\/strong>\uc774\ub77c\ub294 \uc790\ub8cc\uad6c\uc870\uc5d0 \ub300\ud574 \uc124\uba85\ud558\uace0, \uc790\ubc14\ub97c \uc774\uc6a9\ud558\uc5ec \uc774\ub97c \uad6c\ud604\ud558\ub294 \ubc29\ubc95\uc744 \uc54c\uc544\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uc808\ub313\uac12 \ud799\uc740 \uc785\ub825 \ub370\uc774\ud130\uc758 \uc808\ub313\uac12\uc744 \uae30\uc900\uc73c\ub85c \uc6b0\uc120\uc21c\uc704\ub97c \uc815\ud558\ub294 \ud799\uc785\ub2c8\ub2e4.<\/p>\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ub9ac\uc2a4\ud2b8\uc5d0 \ub300\ud574 \uc808\ub313\uac12 \ud799\uc744 \uad6c\ud604\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc808\ub313\uac12 \ud799\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \uae30\ub2a5\uc744 \uc9c0\uc6d0\ud574\uc57c \ud569\ub2c8\ub2e4:<\/p>\n \uad6c\ud604\ub418\ub294 \uc808\ub313\uac12 \ud799\uc758 \uc791\ub3d9 \ubc29\uc2dd\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n \uc785\ub825\uc740 \ub2e4\uc74c\uacfc \uac19\uc740 \ud615\uc2dd\uc73c\ub85c \uc8fc\uc5b4\uc9d1\ub2c8\ub2e4:<\/p>\n \uc5ec\uae30\uc11c N\uc740 \uc5f0\uc0b0\uc758 \uc218\uc774\uba70, \uac01 \uc704\uc758 \uc608\uc81c\uc5d0\uc11c\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \uacfc\uc815\uc744 \ub530\ub985\ub2c8\ub2e4:<\/p>\n \uc774\uc81c \uc808\ub313\uac12 \ud799\uc744 \uc790\ubc14\ub85c \uad6c\ud604\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uae30\ubcf8\uc801\uc73c\ub85c, \uc790\ubc14\uc5d0\uc11c\ub294 PriorityQueue\ub97c \uc0ac\uc6a9\ud558\uc5ec \ud799\uc744 \uad6c\ud604\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uadf8\ub7ec\ub098 \uc774 \uacbd\uc6b0\uc5d0\ub294 \uc808\ub313\uac12\uc744 \uae30\uc900\uc73c\ub85c \uc6b0\uc120\uc21c\uc704\ub97c \uc124\uc815\ud574\uc57c \ud558\ubbc0\ub85c, \ub2e4\uc74c\uacfc \uac19\uc774 Comparator\ub97c \uc791\uc131\ud569\ub2c8\ub2e4.<\/p>\n \ud799\uc5d0\uc11c \uc800\uc7a5\ud560 \ub370\uc774\ud130 \uad6c\uc870\uccb4\ub97c \ub9cc\ub4ed\ub2c8\ub2e4. \uc5ec\uae30\uc11c \uac01 \uc22b\uc790\uc758 \uc6d0\ub798 \uac12\uacfc \uc808\ub313\uac12\uc744 \uc800\uc7a5\ud560 \uac83\uc785\ub2c8\ub2e4.<\/p>\n \uc808\ub313\uac12\uc73c\ub85c \ube44\uad50\ud560 \uc218 \uc788\ub294 Comparator\ub97c \uc815\uc758\ud569\ub2c8\ub2e4.<\/p>\n \uc774\uc81c \uc2e4\uc81c \uc808\ub313\uac12 \ud799\uc744 \uad6c\ud604\ud558\ub294 \ud074\ub798\uc2a4\ub97c \uc0dd\uc131\ud569\ub2c8\ub2e4.<\/p>\n \uc55e\uc11c \uad6c\ud604\ud55c \ud074\ub798\uc2a4\ub4e4\uc744 \uc0ac\uc6a9\ud558\uc5ec \uba54\uc778 \uba54\uc18c\ub4dc\ub97c \uc791\uc131\ud569\ub2c8\ub2e4.<\/p>\n \uc808\ub313\uac12 \ud799\uc744 \uad6c\ud604\ud558\ub294 \uacfc\uc815\uc5d0\uc11c\ub294 \uc0c1\ud669\uc5d0 \ub9de\ub294 Comparator\ub97c \uc815\uc758\ud558\ub294 \uac83\uc774 \ub9e4\uc6b0 \uc911\uc694\ud569\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ubd80\uc5ec\ubc1b\uc740 \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \ud6a8\uc728\uc801\uc778 \uc790\ub8cc\uad6c\uc870\ub97c \uad6c\ucd95\ud560 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4. \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc774\uc640 \uac19\uc740 \ubb38\uc81c\ub294 \ube44\uc2b7\ud55c \ud615\ud0dc\uc758 \uc54c\uace0\ub9ac\uc998 \uc9c8\ubb38\uc73c\ub85c \uc790\uc8fc \ucd9c\uc81c\ub418\ubbc0\ub85c, \ucda9\ubd84\ud55c \uc5f0\uc2b5\uc744 \ud1b5\ud574 \uc219\ub2ec\ud558\ub294 \uac83\uc774 \uc911\uc694\ud569\ub2c8\ub2e4. \uc55e\uc73c\ub85c\ub3c4 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998\uacfc \uc790\ub8cc\uad6c\uc870\ub97c \uc5f0\uc2b5\ud558\uc5ec \ub354 \ub098\uc740 \ud504\ub85c\uadf8\ub798\uba38\uac00 \ub418\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!<\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"\ubb38\uc81c \uc124\uba85<\/h2>\n
\n
\n
\uc785\ucd9c\ub825 \ud615\uc2dd<\/h2>\n
\n N\n operation[0]\n operation[1]\n ...\n operation[N-1] \n <\/pre>\n
operation[i]<\/code>\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n\n
0<\/code>: \uc808\ub313\uac12 \ud799\uc5d0\uc11c \uac00\uc7a5 \uc791\uc740 \uac12\uc744 \uc81c\uac70\ud558\uace0 \ucd9c\ub825\ud558\uc2ed\uc2dc\uc624.<\/li>\nx<\/code>: \uc808\ub313\uac12 \ud799\uc5d0 x<\/code>\ub97c \ucd94\uac00\ud558\uc2ed\uc2dc\uc624.<\/li>\n<\/ul>\n\uc608\uc81c<\/h2>\n
\uc785\ub825<\/h3>\n
\n 7\n 5\n 3\n 6\n 0\n -2\n 4\n 0\n <\/pre>\n
\ucd9c\ub825<\/h3>\n
\n -2\n 3\n <\/pre>\n
\n
\uc808\ub313\uac12 \ud799 \uad6c\ud604 \uacfc\uc815<\/h2>\n
1\ub2e8\uacc4: \ud799 \ub178\ub4dc \uc815\uc758<\/h3>\n
\n class AbsHeapNode {\n int value;\n\n public AbsHeapNode(int value) {\n this.value = value;\n }\n\n public int getAbs() {\n return Math.abs(value);\n }\n }\n <\/pre>\n2\ub2e8\uacc4: Comparator \uc815\uc758<\/h3>\n
\n class AbsMinComparator implements Comparator<AbsHeapNode> {\n @Override\n public int compare(AbsHeapNode a, AbsHeapNode b) {\n if (a.getAbs() != b.getAbs()) {\n return Integer.compare(a.getAbs(), b.getAbs());\n }\n return Integer.compare(a.value, b.value);\n }\n }\n <\/pre>\n3\ub2e8\uacc4: \uc808\ub313\uac12 \ud799 \uad6c\ud604<\/h3>\n
\n import java.util.PriorityQueue;\n\n public class AbsHeap {\n private PriorityQueue<AbsHeapNode> heap;\n\n public AbsHeap() {\n heap = new PriorityQueue<>(new AbsMinComparator());\n }\n\n public void insert(int value) {\n heap.offer(new AbsHeapNode(value));\n }\n\n public Integer removeMin() {\n AbsHeapNode node = heap.poll();\n return (node != null) ? node.value : null;\n }\n }\n <\/pre>\n4\ub2e8\uacc4: \uba54\uc778 \uba54\uc18c\ub4dc \uad6c\ud604<\/h3>\n
\n import java.util.Scanner;\n\n public class Main {\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n AbsHeap absHeap = new AbsHeap();\n int N = scanner.nextInt();\n\n for (int i = 0; i < N; i++) {\n int operation = scanner.nextInt();\n if (operation == 0) {\n Integer minValue = absHeap.removeMin();\n System.out.println(minValue != null ? minValue : 0);\n } else {\n absHeap.insert(operation);\n }\n }\n\n scanner.close();\n }\n }\n <\/pre>\n\uacb0\ub860<\/h2>\n