๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋ก์šฐ์„ ์ˆœ์œ„ํ (3)

๐˜š๐˜ญ๐˜ฐ๐˜ธ ๐˜ฃ๐˜ถ๐˜ต ๐˜ด๐˜ต๐˜ฆ๐˜ข๐˜ฅ๐˜บ

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ๋” ๋งต๊ฒŒ - C++

๋ฌธ์ œ ๋งค์šด ๊ฒƒ์„ ์ข‹์•„ํ•˜๋Š” Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ณ  ์‹ถ์Šต๋‹ˆ๋‹ค. ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด Leo๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ ๊ฐ€์žฅ ๋‚ฎ์€ ๋‘ ๊ฐœ์˜ ์Œ์‹์„ ์•„๋ž˜์™€ ๊ฐ™์ด ํŠน๋ณ„ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์„ž์–ด ์ƒˆ๋กœ์šด ์Œ์‹์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์„ž์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ = ๊ฐ€์žฅ ๋งต์ง€ ์•Š์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ + (๋‘ ๋ฒˆ์งธ๋กœ ๋งต์ง€ ์•Š์€ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ * 2) Leo๋Š” ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๊ฐ€ K ์ด์ƒ์ด ๋  ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•˜์—ฌ ์„ž์Šต๋‹ˆ๋‹ค. Leo๊ฐ€ ๊ฐ€์ง„ ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด scoville๊ณผ ์›ํ•˜๋Š” ์Šค์ฝ”๋นŒ ์ง€์ˆ˜ K๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์Œ์‹์˜ ์Šค์ฝ”๋นŒ ์ง€์ˆ˜๋ฅผ K ์ด์ƒ์œผ๋กœ ๋งŒ๋“ค๊ธฐ ์œ„ํ•ด ์„ž์–ด์•ผ ํ•˜๋Š” ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”. ์ œํ•œ ์‚ฌํ•ญ scoville์˜..

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํ”„๋กœ์„ธ์Šค - C++

๋ฌธ์ œ ์šด์˜์ฒด์ œ์˜ ์—ญํ•  ์ค‘ ํ•˜๋‚˜๋Š” ์ปดํ“จํ„ฐ ์‹œ์Šคํ…œ์˜ ์ž์›์„ ํšจ์œจ์ ์œผ๋กœ ๊ด€๋ฆฌํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ์—์„œ๋Š” ์šด์˜์ฒด์ œ๊ฐ€ ๋‹ค์Œ ๊ทœ์น™์— ๋”ฐ๋ผ ํ”„๋กœ์„ธ์Šค๋ฅผ ๊ด€๋ฆฌํ•  ๊ฒฝ์šฐ ํŠน์ • ํ”„๋กœ์„ธ์Šค๊ฐ€ ๋ช‡ ๋ฒˆ์งธ๋กœ ์‹คํ–‰๋˜๋Š”์ง€ ์•Œ์•„๋‚ด๋ฉด ๋ฉ๋‹ˆ๋‹ค. 1. ์‹คํ–‰ ๋Œ€๊ธฐ ํ(Queue)์—์„œ ๋Œ€๊ธฐ์ค‘์ธ ํ”„๋กœ์„ธ์Šค ํ•˜๋‚˜๋ฅผ ๊บผ๋ƒ…๋‹ˆ๋‹ค. 2. ํ์— ๋Œ€๊ธฐ์ค‘์ธ ํ”„๋กœ์„ธ์Šค ์ค‘ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋” ๋†’์€ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์žˆ๋‹ค๋ฉด ๋ฐฉ๊ธˆ ๊บผ๋‚ธ ํ”„๋กœ์„ธ์Šค๋ฅผ ๋‹ค์‹œ ํ์— ๋„ฃ์Šต๋‹ˆ๋‹ค. 3. ๋งŒ์•ฝ ๊ทธ๋Ÿฐ ํ”„๋กœ์„ธ์Šค๊ฐ€ ์—†๋‹ค๋ฉด ๋ฐฉ๊ธˆ ๊บผ๋‚ธ ํ”„๋กœ์„ธ์Šค๋ฅผ ์‹คํ–‰ํ•ฉ๋‹ˆ๋‹ค. 3.1 ํ•œ ๋ฒˆ ์‹คํ–‰ํ•œ ํ”„๋กœ์„ธ์Šค๋Š” ๋‹ค์‹œ ํ์— ๋„ฃ์ง€ ์•Š๊ณ  ๊ทธ๋Œ€๋กœ ์ข…๋ฃŒ๋ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ํ”„๋กœ์„ธ์Šค 4๊ฐœ [A, B, C, D]๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ์‹คํ–‰ ๋Œ€๊ธฐ ํ์— ๋“ค์–ด์žˆ๊ณ , ์šฐ์„ ์ˆœ์œ„๊ฐ€ [2, 1, 3, 2]๋ผ๋ฉด [C, D, A, B] ์ˆœ์œผ๋กœ ์‹คํ–‰ํ•˜๊ฒŒ ๋ฉ๋‹ˆ๋‹ค. ํ˜„์žฌ ์‹ค..

[๋ฐฑ์ค€] 1966๋ฒˆ: ํ”„๋ฆฐํ„ฐ ํ - C++

๋ฌธ์ œ ์—ฌ๋Ÿฌ๋ถ„๋„ ์•Œ๋‹ค์‹œํ”ผ ์—ฌ๋Ÿฌ๋ถ„์˜ ํ”„๋ฆฐํ„ฐ ๊ธฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ๋ถ„์ด ์ธ์‡„ํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฌธ์„œ๋ฅผ ์ธ์‡„ ๋ช…๋ น์„ ๋ฐ›์€ ‘์ˆœ์„œ๋Œ€๋กœ’, ์ฆ‰ ๋จผ์ € ์š”์ฒญ๋œ ๊ฒƒ์„ ๋จผ์ € ์ธ์‡„ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์„œ๊ฐ€ ์Œ“์ธ๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ์— ์Œ“์—ฌ์„œ FIFO - First In First Out - ์— ๋”ฐ๋ผ ์ธ์‡„๊ฐ€ ๋˜๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ์šด ํ”„๋ฆฐํ„ฐ๊ธฐ ๋‚ด๋ถ€ ์†Œํ”„ํŠธ์›จ์–ด๋ฅผ ๊ฐœ๋ฐœํ•˜์˜€๋Š”๋ฐ, ์ด ํ”„๋ฆฐํ„ฐ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์— ๋”ฐ๋ผ ์ธ์‡„๋ฅผ ํ•˜๊ฒŒ ๋œ๋‹ค. ํ˜„์žฌ Queue์˜ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ๋ฌธ์„œ์˜ ‘์ค‘์š”๋„’๋ฅผ ํ™•์ธํ•œ๋‹ค. ๋‚˜๋จธ์ง€ ๋ฌธ์„œ๋“ค ์ค‘ ํ˜„์žฌ ๋ฌธ์„œ๋ณด๋‹ค ์ค‘์š”๋„๊ฐ€ ๋†’์€ ๋ฌธ์„œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ๋‹ค๋ฉด, ์ด ๋ฌธ์„œ๋ฅผ ์ธ์‡„ํ•˜์ง€ ์•Š๊ณ  Queue์˜ ๊ฐ€์žฅ ๋’ค์— ์žฌ๋ฐฐ์น˜ ํ•œ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ๋ฐ”๋กœ ์ธ์‡„๋ฅผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด Queue์— 4๊ฐœ์˜ ๋ฌธ์„œ(A B C D)๊ฐ€ ์žˆ๊ณ , ์ค‘์š”๋„๊ฐ€ 2 ..