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

์œ ๋‹ˆ์˜จํŒŒ์ธ๋“œ

Algorithm/BOJ 2022. 3. 14. [BOJ] ์‚ฌ์ดํด ๊ฒŒ์ž„(20040) [๋ฐฑ์ค€(BOJ)] 20040_์‚ฌ์ดํด ๊ฒŒ์ž„ C++ ๋ฌธ์ œ : BOJ_20040๋ฒˆ ์‚ฌ์ดํด ๊ฒŒ์ž„ ๋ฌธ์ œ ์„ค๋ช… n ๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์ฃผ์–ด์ง€๊ณ , m ๊ฐœ์˜ ์–‘๋ฐฉํ–ฅ ์„ ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ตœ์ดˆ๋กœ ์‚ฌ์ดํด์ด ์™„์„ฑ๋˜๋Š” m ๋ฒˆ ์งธ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ชจ๋“  m์„ ์ˆœํšŒํ•ด๋„ ์‚ฌ์ดํด์ด ์ƒ๊ธฐ์ง€ ์•Š์•˜๋‹ค๋ฉด, 0์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ n์ด ์ตœ๋Œ€ 500,000์ด๋ฏ€๋กœ O(n) ๋งŒ์— ๋‹ต์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด์–ด์ง€๋Š” ๋‘ ์ ์„ merge ํ•˜๋ฉด์„œ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค. merge ํ•˜๊ธฐ ์ „์— ์ฃผ์–ด์ง„ ๋‘ ์ ์ด ๊ฐ™์€ ์กฐ์ƒ์ด๋ผ๋ฉด, ๊ฐ™์€ ์กฐ์ƒ์„ ๊ฐ–๊ณ  ์žˆ๋Š” ๋…ธ๋“œ๋ผ๋ฆฌ ์ด์–ด์ง€๋ฏ€๋กœ ์‚ฌ์ดํด์ด ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ์˜ m์„ ์ถœ๋ ฅํ•ด ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค. Description vector๋ฅผ ์ด์šฉํ•ด n๊ณผ m์— ๊ฐ’์— ๋งž๋Š” ๋ฐฐ์—ด์„ ๋™์ ํ• ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ..

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