๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๊ฐœ์ธ๊ณต๋ถ€/Algorithm

[Level 1] ํ–‰๋ ฌ์˜ ๋ง์…ˆ

by ๐Ÿ‡๋ฐ•๋ด‰๋ด‰๐Ÿ‡ 2021. 3. 28.

 

 

 

Algorithm

-  ํ–‰๋ ฌ์˜ ๋ง์…ˆ -

 


 

๋ฌธ์ œ

ํ–‰๋ ฌ์˜ ๋ง์…ˆ์€ ํ–‰๊ณผ ์—ด์˜ ํฌ๊ธฐ๊ฐ€ ๊ฐ™์€ ๋‘ ํ–‰๋ ฌ์˜ ๊ฐ™์€ ํ–‰, ๊ฐ™์€ ์—ด์˜ ๊ฐ’์„ ์„œ๋กœ ๋”ํ•œ ๊ฒฐ๊ณผ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค.

2๊ฐœ์˜ ํ–‰๋ ฌ arr1๊ณผ arr2๋ฅผ ์ž…๋ ฅ๋ฐ›์•„, ํ–‰๋ ฌ ๋ง์…ˆ์˜ ๊ฒฐ๊ณผ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด ์ฃผ์„ธ์š”.

 

์ž…์ถœ๋ ฅ ์˜ˆ์‹œ

arr1 arr2 return
[[1, 2], [2, 3,]] [[3, 4], [5, 6]] [[4, 6], [7, 9]]
[[1], [2]] [[3], [4]] [[4], [6]]

 

๋ฌธ์ œ ํ’€๊ธฐ

 

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ์ดˆ๋ฐ˜์— ๋ฌธ์ œ์ดํ•ด๋ฅผ ์ œ๋Œ€๋กœ ํ•˜์ง€ ๋ชปํ•ด ์‚ด์ง ํ—ค๋งจ๊ฒƒ๋งŒ ๋นผ๋ฉด ๊ทธ๋ž˜๋„ ๋ฌธ์ œ์˜ ์กฐ๊ฑด์ด ๋„๋„ํ•œ ํŽธ์ด๋ผ ํฐ ๋ฌธ์ œ ์—†์ด ์ž˜ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

 

์ผ๋‹จ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐ›์•„์˜ค๋Š” 2๊ฐœ์˜ ํ–‰๋ ฌ์˜ ๊ธธ์ด๊ฐ€ ์ผ์น˜ํ•ด์„œ ์ค‘๊ฐ„์— ๋น„์–ด์žˆ๋‹ค๊ฑฐ๋‚˜ ์˜ค๋ฐ”๋˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒ๋˜์ง€ ์•Š์•„์„œ ๋”ฐ๋กœ ์กฐ๊ฑด์„ ์‚ฌ์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ํ•„์š”๋Š” ์—†์—ˆ๋‹ค.

(์•„๋งˆ ์žˆ์—ˆ๋‹ค๋ฉด ๋จธ๋ฆฌ๊ฐ€ ์•„ํ”„์ง€ ์•Š์•˜์„๊นŒ...ใ…Žใ…Žใ…Ž)

 

๊ทธ๋ž˜์„œ ์ผ๋‹จ์€ ์ดˆ๋ฐ˜์—๋Š” result์•ˆ์— ๊ฐ’์„ pushํ•˜๋Š” ์›๋ฆฌ๊ฐ€ ์•„๋‹ˆ๋ผ ๋ฐ”๋กœ ์ธ๋ฑ์Šค๋ฅผ ํ†ตํ•ด ๊ฐ’์„ ์ฐ์–ด๋ฒ„๋ฆฌ๋Š” ํ˜•์‹์œผ๋กœ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด๋ณด๋ ค๊ณ  ํ•˜์˜€์œผ๋‚˜ ์ƒ๊ฐํ•ด๋ณด๋‹ˆ result์˜ n๋ฒˆ์งธ ์•ˆ์—๋Š” ๊ฐ’์ด ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ์„์ง€ ๋ชฐ๋ผ๋„ result์˜ n๋ฒˆ์จฐ ์•ˆ์— ์žˆ๋Š” ๋ฐฐ์—ด m๋ฒˆ์งธ์— ๋„ฃ๋Š” ๊ฒƒ์€ ์• ์ดˆ์— ๊ทธ์•ˆ์— ๋‚ด๊ฐ€ ๋นˆ๋ฐฐ์—ด์„ ๋„ฃ์–ด์ค€ ๊ฒƒ์ด ์•„๋‹ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ฌธ์ œ๊ฐ€ ํ•ด๊ฒฐ๋ ํ„ฐ๊ฐ€ ์žˆ๋‚˜....

 

๊ทธ๋ž˜์„œ ๋‹ค๋ฅธ ๋ฐฉ๋ฒ•์„ ์ƒ๊ฐํ•ด ๋‚ธ๊ฒŒ ์šฐ์„  ๋ฐ˜๋ณต๋ฌธ 2๊ฐœ๋ฅผ ํ†ตํ•ด์„œ ๊ฐ’์„ ๋„ฃ์–ด์ฃผ๋ ค๊ณ  ํ•˜์˜€์œผ๋ฉฐ ์ด๋•Œ ์•ˆ์— ์žˆ๋Š” ๋ฐ˜๋ณต๋ฌธ์— ๋“ค์–ด๊ฐ€๊ธฐ ์ „์— value๋ผ๋Š” ๋นˆ๋ฐฐ์—ด์„ ๋งŒ๋“ ๋‹ค์Œ์— ์•ˆ์— ์žˆ๋Š” ๋ฐ˜๋ณต๋ฌธ์€ ๊ฐ ํ–‰๋ ฌ์˜ ๊ฐ’์„ ๋”ํ•œ ๊ฐ’์„ value์•ˆ์— ๋„ฃ์€ ๋‹ค์Œ์— ์•ˆ์ชฝ ๋ฐ˜๋ณต๋ฌธ์ด ๋‹ค ๋Œ์•„๊ฐ€๊ฒŒ ๋˜๋ฉด ๊ทธ ์ดํ›„์— ๋ฐฐ์—ด ํ†ต์งธ๋กœ result์•ˆ์— ๊ฐ’์„ ๋„ฃ์–ด์ฃผ๋Š” ๋ฐฉ๋ฒ•์„ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•ด ๋ณด์•˜๋‹ค.

 

์ผ๋‹จ ์–ด์ฐŒ์–ด์ฐŒ ๋ฌธ์ œ๋Š” ํ•ด๊ฒฐํ•˜์˜€์œผ๋‚˜ ๊ฐ„๋‹จํ•œ ์›๋ฆฌ์น˜๊ณ ๋Š” ์ฝ”๋“œ๊ฐ€ ์ข€ ๊ธธ๊ฒŒ ๋Š๊ปด์ ธ์„œ ๋‹ค๋ฅธ ๋ถ„๋“ค์ด ์ž‘์„ฑํ•œ ํ•ด๋‹ต์„ ํ™•์ธํ•ด๋ณด๋‹ˆ map์•ˆ์— map์„ ๋„ฃ์–ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•œ ๊ฒƒ์„ ๋ณด๊ณ  ์™œ ๋‚œ ์ด์ƒ๊ฐ์„ ๋ชปํ–ˆ๋Š”์ง€... ๊ทธ๋ž˜๋„ ์ƒˆ๋กœ์šด ๋ฐฉ๋ฒ•์„ ์•Œ๊ฒŒ๋œ ๊ณ„๊ธฐ๊ฐ€ ๋˜์–ด์„œ ๋‹คํ–‰์ธ ๊ฒƒ ๊ฐ™๋‹ค.

 

 

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€