๋ชฉ๋ก์•Œ๊ณ ๋ฆฌ์ฆ˜ (4)

'๊ฐœ๋ฐœ'์ž๊ตญ ๐Ÿพ

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํž™(Heap) ๋” ๋งต๊ฒŒ _ ์ž๋ฐ”Java

๋‚œ์ด๋„: Level 2 1. ๋ฌธ์ œ https://programmers.co.kr/learn/courses/30/lessons/42626 ์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ๋” ๋งต๊ฒŒ ๋งค์šด ๊ฒƒ์„ ์ข‹์•„ํ•˜๋Š” Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด Leo๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ๋‘ ๊ฐœ์˜ ์Œ์‹์„ ์•„๋ž˜์™€ ๊ฐ™๏ฟฝ๏ฟฝ programmers.co.kr | ๋ฌธ์ œ ์„ค๋ช… ๋งค์šด ๊ฒƒ์„ ์ข‹์•„ํ•˜๋Š” Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด Leo๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ๋‘ ๊ฐœ์˜ ์Œ์‹์„ ์•„๋ž˜์™€ ๊ฐ™์ด ํŠน๋ณ„ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์„ž์–ด ์ƒˆ๋กœ์šด ์Œ์‹์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์„ž์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ = ๊ฐ€์žฅ ๋งต์ง€ ์•Š์€ ์Œ์‹์˜ ..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํ•ด์‹œ(Hash) ์ „ํ™”๋ฒˆํ˜ธ ๋ชฉ๋ก _ ์ž๋ฐ”Java

๋‚œ์ด๋„: Level 2 1. ๋ฌธ์ œ | ๋ฌธ์ œ ์„ค๋ช… ์ „ํ™”๋ฒˆํ˜ธ๋ถ€์— ์ ํžŒ ์ „ํ™”๋ฒˆํ˜ธ ์ค‘, ํ•œ ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ๊ฐ€ ์žˆ๋Š”์ง€ ํ™•์ธํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค. ์ „ํ™”๋ฒˆํ˜ธ๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™์„ ๊ฒฝ์šฐ, ๊ตฌ์กฐ๋Œ€ ์ „ํ™”๋ฒˆํ˜ธ๋Š” ์˜์„์ด์˜ ์ „ํ™”๋ฒˆํ˜ธ์˜ ์ ‘๋‘์‚ฌ์ž…๋‹ˆ๋‹ค. ๊ตฌ์กฐ๋Œ€ : 119 ๋ฐ•์ค€์˜ : 97 674 223 ์ง€์˜์„ : 11 9552 4421 ์ „ํ™”๋ฒˆํ˜ธ๋ถ€์— ์ ํžŒ ์ „ํ™”๋ฒˆํ˜ธ๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด phone_book ์ด solution ํ•จ์ˆ˜์˜ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์–ด๋–ค ๋ฒˆํ˜ธ๊ฐ€ ๋‹ค๋ฅธ ๋ฒˆํ˜ธ์˜ ์ ‘๋‘์–ด์ธ ๊ฒฝ์šฐ๊ฐ€ ์žˆ์œผ๋ฉด false๋ฅผ ๊ทธ๋ ‡์ง€ ์•Š์œผ๋ฉด true๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. | ์ œํ•œ ์‚ฌํ•ญ phone_book์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 1,000,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค. ๊ฐ ์ „ํ™”๋ฒˆํ˜ธ์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 20 ์ดํ•˜์ž…๋‹ˆ๋‹ค. | ์ž…์ถœ๋ ฅ ์˜ˆ์ œ ph..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๊นŠ์ด/๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(DFS/BFS) ํƒ€๊ฒŸ๋„˜๋ฒ„ _ ์ž๋ฐ”Java

๋‚œ์ด๋„: Level 2 1. ๋ฌธ์ œ | ๋ฌธ์ œ ์„ค๋ช… n๊ฐœ์˜ ์Œ์ด ์•„๋‹Œ ์ •์ˆ˜๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ˆ˜๋ฅผ ์ ์ ˆํžˆ ๋”ํ•˜๊ฑฐ๋‚˜ ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“ค๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด [1, 1, 1, 1, 1]๋กœ ์ˆซ์ž 3์„ ๋งŒ๋“ค๋ ค๋ฉด ๋‹ค์Œ ๋‹ค์„ฏ ๋ฐฉ๋ฒ•์„ ์“ธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์ˆซ์ž๊ฐ€ ๋‹ด๊ธด ๋ฐฐ์—ด numbers, ํƒ€๊ฒŸ ๋„˜๋ฒ„ target์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ ์ˆซ์ž๋ฅผ ์ ์ ˆํžˆ ๋”ํ•˜๊ณ  ๋นผ์„œ ํƒ€๊ฒŸ ๋„˜๋ฒ„๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. | ์ œํ•œ ์‚ฌํ•ญ ์ฃผ์–ด์ง€๋Š” ์ˆซ์ž์˜ ๊ฐœ์ˆ˜๋Š” 2๊ฐœ ์ด์ƒ 20๊ฐœ ์ดํ•˜์ž…๋‹ˆ๋‹ค. ๊ฐ ์ˆซ์ž๋Š” 1 ์ด์ƒ 50 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค. ํƒ€๊ฒŸ ๋„˜๋ฒ„..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํƒ์š•๋ฒ•(Greedy) ๊ตฌ๋ช…๋ณดํŠธ _ ์ž๋ฐ”Java

๋‚œ์ด๋„: Level 2 1. ๋ฌธ์ œ | ๋ฌธ์ œ ์„ค๋ช… ๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ๋ช…๋ณดํŠธ๋Š” ์ž‘์•„์„œ ํ•œ ๋ฒˆ์— ์ตœ๋Œ€ 2๋ช…์”ฉ ๋ฐ–์— ํƒˆ ์ˆ˜ ์—†๊ณ , ๋ฌด๊ฒŒ ์ œํ•œ๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ [70kg, 50kg, 80kg, 50kg]์ด๊ณ  ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์ด 100kg์ด๋ผ๋ฉด 2๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 4๋ฒˆ์งธ ์‚ฌ๋žŒ์€ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์žˆ์ง€๋งŒ 1๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 3๋ฒˆ์งธ ์‚ฌ๋žŒ์˜ ๋ฌด๊ฒŒ์˜ ํ•ฉ์€ 150kg์ด๋ฏ€๋กœ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์„ ์ดˆ๊ณผํ•˜์—ฌ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ตœ๋Œ€ํ•œ ์ ๊ฒŒ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด people๊ณผ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ limit๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ๊ตฌ๋ช…๋ณดํŠธ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„..