๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

Design HashMap1

[์ž๋ฐ”] ๋ฆฌํŠธ์ฝ”๋“œ 706 - Design HashMap HashMap์€ Map์„ ๊ตฌํ˜„ํ•œ ํด๋ž˜์Šค์ด๊ธฐ ๋•Œ๋ฌธ์—, ํ˜•ํƒœ๋กœ ๋ฐ์ดํ„ฐ๊ฐ€ ๋“ค์–ด๊ฐ„๋‹ค. ํ•ญ์ƒ ์ฃผ์–ด์ง„ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉ๋งŒ ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์—, ์–ด๋–ป๊ฒŒ ๊ตฌํ˜„๋˜์–ด ์žˆ๋Š”์ง€์— ๋Œ€ํ•ด์„œ๋Š” ๊ณ ๋ฏผํ•ด๋ณด์ง€ ์•Š์•˜๋Š”๋ฐ ๋•๋ถ„์— bucket์ด๋ผ๋Š” ๊ฐœ๋…๋„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. ์ด๋ฒˆ ๋ฌธ์ œ๋Š” ๊ณต๋ถ€ํ•˜๋Š” ์ฐจ์›์—์„œ ํ‘ผ ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์—, ๋ฐ”๋กœ ํ’€์ด๋“ค์„ ์ข€ ์ฐพ์•„ ๋ณด์•˜๋‹ค. ์ฒซ ๋ฒˆ์งธ Solution ์–ด์ฐจํ”ผ key์˜ ๋ฒ”์œ„๊ฐ€ 0๋ถ€ํ„ฐ 1,000,000, ์ฆ‰ ๋ฐฑ๋งŒ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฐ์—ด์„ ์ƒ์„ฑํ•ด์„œ ๊ตฌํ˜„ํ•ด๋„ ๋ฌธ์ œ๊ฐ€ ์—†๋‹ค. MyHashMap ํด๋ž˜์Šค ์ƒ์„ฑ ์‹œ์—, ํฌ๊ธฐ 1000001์ธ ๋ฐฐ์—ด์„ ์„ ์–ธํ•œ ๋‹ค์Œ์— index๋ฅผ ํ‚ค๊ฐ’์ฒ˜๋Ÿผ ์ƒ๊ฐํ•ด์„œ ๊ตฌํ˜„ํ•˜๋ฉด ๋œ๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„ : O(1) (get, remove, put ๋ชจ๋‘์— ํ•ด๋‹น๋œ๋‹ค) ๊ณต๊ฐ„ ๋ณต์žก๋„ : O(n) class MyHashMap { int[] .. 2021. 3. 7.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”