ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค) ์™„์ฃผํ•˜์ง€ ๋ชปํ•œ ์„ ์ˆ˜ (Hash)

ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค) ์™„์ฃผํ•˜์ง€ ๋ชปํ•œ ์„ ์ˆ˜ ๋‚ด ํ’€์ด ๊ตฌํ˜„์€ ์‰ฌ์šฐ๋‚˜, ์–ด๋–ป๊ฒŒ ํšจ์œจ์ ์œผ๋กœ ๋Œ๋ฆด์ง€ ๊ณ ๋ฏผ Sorting์„ ํ•˜์—ฌ, ์ฐจ๋ก€๋Œ€๋กœ ํ™•์ธํ•˜๋‹ค๊ฐ€ ๊ฐ’์ด ๋‹ค๋ฅด๋ฉด ํ•ด๋‹น๊ฐ’์„ ๋ฆฌํ„ดํ•œ๋‹ค. ์˜ˆ์™ธ์ฒ˜๋ฆฌ : ๋ฏธ์™„์ฃผ์ž๊ฐ€ participant์˜ ๋งจ๋งˆ์ง€๋ง‰์— ์œ„์น˜ํ•  ๊ฒฝ์šฐ, for๋ฌธ์•ˆ์—์„œ ํ•ด๊ฒฐ๋˜์ง€์•Š์œผ๋ฏ€๋กœ ๋ณ„๋„๋กœ ๋งˆ์ง€๋ง‰ ๊ฐ’ ๋ฆฌํ„ด v2 Hash ์นดํ…Œ๊ณ ๋ฆฌ์— ์œ„์น˜ํ–ˆ๊ธฐ ๋•Œ๋ฌธ์—, ์ฒ˜์Œ ๊ณ ๋ฏผํ• ๋•Œ ์ƒ๊ฐํ–ˆ๋˜ ๋ฐฉ๋ฒ•. participant๋Š” 1์„ ๋”ํ•˜๊ณ  completion์„ 1์„ ๋บ€ ํ›„, 0์ด ์•„๋‹ˆ๋ฉด ๋ฆฌํ„ดํ•˜๋Š” ๋ฐฉ์‹ map.getOrDefault(~, ~) ๋ฉ”์†Œ๋“œ๊ฐ€ ์ƒ๊ฐ๋‚˜์ง€ ์•Š์•„ ๊ตฌํ˜„๋ณด๋ฅ˜. Collections Framework์— ๋Œ€ํ•ด ๋”๋”์šฑ ์ž˜ ์•Œ๋„๋ก ํ•˜์ž. v3 ๋‚ด ๋ฐฉ์‹์ด๋ž‘ ๋˜‘๊ฐ™๋‹ค. ๋‹ค๋งŒ ๋‚˜์ฒ˜๋Ÿผ ๋ณ„๋„๋กœ List ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ƒ์„ฑํ•  ํ•„์š”๊ฐ€ ์—†์—ˆ๋‹ค. sorting์„..

Algorithm_Q 2019. 9. 13. 15:51
์ž๋ฃŒ๊ตฌ์กฐ) Hash (ํ•ด์‹œ)

Hash (ํ•ด์‹œ) Input Output ์ฒซ ์ค„์— ๋ช…๋ น์–ด์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. (1 ≤ V ≤ 100,000) ๋‘๋ฒˆ์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ์•„๋ž˜์™€ ๊ฐ™์€ ํ˜•ํƒœ๋กœ ๋ช…๋ น์–ด๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. 1 s: ์ž…๋ ฅ๋ฐ›์€ ๋ฌธ์ž์—ด s๋ฅผ set์— ์ถ”๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฏธ set์— ์กด์žฌํ•œ๋‹ค๋ฉด ์ถ”๊ฐ€ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. 2 s: ์ž…๋ ฅ๋ฐ›์€ ๋ฌธ์ž์—ด s๋ฅผ set์—์„œ ์ œ๊ฑฐํ•ฉ๋‹ˆ๋‹ค. ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด ์•„๋ฌด ๋™์ž‘๋„ ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. 3 s: ์ž…๋ ฅ๋ฐ›์€ ๋ฌธ์ž์—ด s๊ฐ€ set์— ์žˆ๋‹ค๋ฉด 1์„, ์—†๋‹ค๋ฉด 0์„ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ๋ช…๋ น์–ด์— ์•Œ๋งž์€ ๊ฒฐ๊ณผ๋ฅผ ํ•œ์ค„์”ฉ ์ถœ๋ ฅํ•ฉ๋‹ˆ๋‹ค. import java.util.*; public class Test { public static void main(String args[]) { Scanner sc = new Scanner(System...

Data Structure 2019. 9. 12. 19:02
๊ณต์ง€์‚ฌํ•ญ
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€
Total
Today
Yesterday
๋งํฌ
ยซ   2024/11   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
๊ธ€ ๋ณด๊ด€ํ•จ