[Algorithm] - 2022 ์นด์นด์˜ค ์‹ ์ž… 1์ฐจ ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ (Kakao Newbie Primary Online Coding Test) for Tech developers ๋ฌธ์ œ ํ’€์ด

๋ฐ˜์‘ํ˜•

๋งค๋…„ ์ด๋ค„์ง€๋Š” ์นด์นด์˜ค ์‹ ์ž… ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ’€์ด๋ฅผ ๋˜ ์ ๊ฒŒ ๋˜์—ˆ๋„ค์š”. ํšŒ์‚ฌ ์—…๋ฌด๋ฅผ ์ข€ ๋” ์‹ ๊ฒฝ์จ์•ผ ํ•˜๋‹ค๋ณด๋‹ˆ ๋งˆ๋ƒฅ ํ‘ธ๋Š” ๊ฒƒ์„ ๋ฏธ๋ค„๋†“๊ณ ๋งŒ ์žˆ๋‹ค ์ด์ œ์„œ์•ผ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•˜๊ฒŒ ๋˜์—ˆ์Šต๋‹ˆ๋‹ค.

 

์ด๋ฒˆ์—๋„ ๋จผ์ € ๋ฌธ์ œ ํ’€์ด ์ „ ํ›„๊ธฐ๋ฅผ ์ž ๊น ๋ง์”€๋“œ๋ฆฌ์ž๋ฉด ์ž‘๋…„ ๋ฌธ์ œ์— ๋น„ํ•˜์—ฌ ๋‚œ์ด๋„๊ฐ€ ๋งŽ์ด ๊ฐœ์„ ๋œ ๋ชจ์Šต์ด์—ˆ์Šต๋‹ˆ๋‹ค. ์ž‘๋…„๊ณผ ๋‹ฌ๋ฆฌ Lv 4 ๋ฌธ์ œ๋Š” ์ถœ์ œ ๋˜์ง€ ์•Š์•˜๊ณ , ๊ตฌํ˜„ ์ค‘์‹ฌ์˜ ์•ž ๋ฌธ์ œ์™€ ์ข€ ๋” ์‹ค๋ ฅ์„ ๋ณด๊ธฐ ์œ„ํ•œ Lv 3 ๋‚œ์ด๋„ ๋ฌธ์ œ 1~2๋ฌธ์ œ๋กœ ์ถ”๋ ค์ง„ ๋ชจ์Šต์ด์—ˆ์Šต๋‹ˆ๋‹ค.

 

๊ทธ๋Ÿผ ๋ฌธ์ œ ํ’€์ด๋ฅผ ์ง„ํ–‰ํ•ด๋ณด๊ฒ ์Šต๋‹ˆ๋‹ค.

 

 

 

Question 01. ์‹ ๊ณ  ๊ฒฐ๊ณผ ๋ฐ›๊ธฐ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92334)

 

์‹ ์ž…์‚ฌ์› ๋ฌด์ง€๋Š” ๊ฒŒ์‹œํŒ์˜ ๋ถˆ๋Ÿ‰ ์ด์šฉ์ž๋ฅผ ์‹ ๊ณ ํ•˜๊ณ  ์ฒ˜๋ฆฌ ๊ฒฐ๊ณผ๋ฅผ ๋ฉ”์ผ๋กœ ๋ฐœ์†กํ•˜๋Š” ์‹œ์Šคํ…œ์„ ๊ฐœ๋ฐœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ํŠน์ • ์กฐ๊ฑด์— ํ•ด๋‹นํ•˜๋Š” ๊ฒŒ์‹œํŒ ๋ถˆ๋Ÿ‰ ์ด์šฉ์ž๋ฅผ ์ฐพ์•„ ๋ˆ„์  ์‹ ๊ณ  ํšŸ์ˆ˜๊ฐ€ ์ž„๊ณ„์น˜๋ฅผ ๋„˜์€ ์ด์šฉ์ž๋ฅผ ์ถ”๋ ค๋‚ด๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

(์ด์ „ ๊ธ€๊ณผ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ ๋ฌธ์ œ์— ๋Œ€ํ•œ ์ƒ์„ธ ์‚ฌํ•ญ์€ ์ƒ๋žตํ•ฉ๋‹ˆ๋‹ค. ์ž์„ธํ•œ ๋ฌธ์ œ๋Š” ๋ฌธ์ œ ์›๋ฌธ์„ ์ฐธ๊ณ ํ•ด์ฃผ์„ธ์š”.)

 

 

Solution for Question 01

1๋ฒˆ ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ์กฐ๊ฑด์„ ์ž˜ ์ดํ•ดํ•˜๊ณ  ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๋ณด๋Š” ๊ธฐ์ดˆ์ ์ธ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ž‘๋…„๊ณผ ๊ฐ™์ด 1๋ฒˆ ๋ฌธ์ œ๋Š” ์ฃผ์–ด์ง„ ์š”๊ตฌ์‚ฌํ•ญ์„ ์ž˜ ์ดํ•ดํ•˜๊ณ  ๋‚ด๊ฐ€ ์ž์‹  ์žˆ๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด๋กœ ์ž˜ ๊ตฌํ˜„ํ•˜๋Š”์ง€๋ฅผ ๋ณด๋Š” ๋ฌธ์ œ ๊ฐ™์•˜์Šต๋‹ˆ๋‹ค. ์ •๋‹ต๋ฅ ์ด ๋ฌด๋ ค 80%๊ฐ€ ๋„˜๋Š”๊ตฐ์š”.

 

Map๊ณผ Stream์„ ์ด์šฉํ•ด์„œ ํ’€๋ฉด filter๋ฅผ ์ด์šฉํ•ด ํŠน์ • ์ž„๊ณ„๊ฐ’์„ ๋„˜๋Š” ๊ตฌ๊ฐ„๋งŒ์„ ๋ฆฌ์ŠคํŠธ๋กœ ์žฌ๊ฐ€๊ณตํ•ด์„œ ๋ณด์—ฌ์ค„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์™ธ์—๋„ ์ง์ ‘ for Loop์„ ์‚ฌ์šฉํ•  ์ˆ˜๋„ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค.

 

 

 

Question 02. k ์ง„์ˆ˜์—์„œ ์†Œ์ˆ˜์˜ ๊ฐฏ์ˆ˜ ๊ตฌํ•˜๊ธฐ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92335)

 

์–‘์˜ ์ •์ˆ˜ n์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด ์ˆซ์ž๋ฅผ k ์ง„์ˆ˜๋กœ ๋ฐ”๊ฟจ์„ ๋•Œ, ๋ณ€ํ™˜๋œ ์ˆ˜ ์•ˆ์— ํŠน์ • ์กฐ๊ฑด์— ๋งž๋Š” ์†Œ์ˆ˜(Prime number)๊ฐ€ ๋ช‡ ๊ฐœ์ธ์ง€ ์•Œ๋ ค์ฃผ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 02

2๋ฒˆ ๋ฌธ์ œ๋„ 1๋ฒˆ ๋ฌธ์ œ์™€ ๋น„์Šทํ•˜์ง€๋งŒ ๋‹จ์ˆœํžˆ ์ฃผ์–ด์ง„ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•ด์„œ ๊ตฌํ˜„ํ•˜๊ธฐ ๋ณด๋‹จ ์–ธ์–ด์—์„œ ์ œ๊ณตํ•˜๋Š” API๋‚˜ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‘์šฉํ•˜์—ฌ ์ฃผ์–ด์ง„ ๋ฌธ์ œ๋ฅผ ์–ด๋–ค์‹์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š”์ง€๋ฅผ ๋ณด๊ณ ์ž ํ•˜๋Š” ๋ฌธ์ œ์˜€๋˜ ๊ฒƒ ๊ฐ™์•˜์Šต๋‹ˆ๋‹ค. 

 

๋จผ์ € ๊ตฌํ˜„ํ•ด์•ผ ํ•  ๊ฒƒ์€ ๋ฐ”๋กœ ์ง„๋ฒ•์„ ์–ด๋–ป๊ฒŒ ๋ณ€ํ™˜ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. n์ด 1 ~ 1,000,000 ๊ธธ์ด๊นŒ์ง€์ด๊ณ , k๋Š” 3 ~ 10๊นŒ์ง€์ด๋ฏ€๋กœ 1,000,000 ๊ธธ์ด๋ฅผ 3์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•˜๋ฉด ์ตœ๋Œ€ ๊ธธ์ด๋Š” 1,212,210,202,001๊ธธ์ด ์ž…๋‹ˆ๋‹ค.์‹ค์ œ๋กœ ์ด ๊ธธ์ด๋Š” ์šฐ๋ฆฌ๊ฐ€ ์‚ฌ์šฉํ•˜๋Š” int ๋ฒ”์œ„๋ณด๋‹ค ํ›จ์”ฌ ๊ธธ๊ธฐ ๋•Œ๋ฌธ์— ๋‹ค๋ฅธ ํƒ€์ž…์„ ์ด์šฉํ•ด์„œ ์ง„๋ฒ• ๋ณ€ํ™˜์„ ์ˆ˜ํ–‰ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

๊ฐ„๋‹จํ•˜๊ฒŒ๋Š” String ํƒ€์ž…์„ ์ด์šฉํ•ด๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Python ์–ธ์–ด๋ผ๋ฉด ์ผ๋ฐ˜์ ์ธ String์„ ์‚ฌ์šฉํ•ด๋ณด๊ฑฐ๋‚˜ list๋ฅผ ์‚ฌ์šฉํ•ด๋ณผ ์ˆ˜ ์žˆ์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ๋ฐ˜๋ฉด Java์—์„œ๋Š” StringBuilder๊ฐ€ ์กด์žฌํ•˜๋Š”๋ฐ, Java์˜ StringBuilder๊ฐ€ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ capacity๋Š” 2147483647 ๊ธธ์ด๋ผ๋Š” ์ ์„ ๊ฐ์•ˆํ–ˆ์„ ๋•Œ ์‹ค์ œ๋กœ ์ด ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ์ตœ์ ์˜ ์กฐ๊ฑด์€ ์•„๋‹™๋‹ˆ๋‹ค.

 

ํ•˜์ง€๋งŒ ์•„์ด๋Ÿฌ๋‹ˆํ•˜๊ฒŒ๋„ StringBuilder๋ฅผ ์‚ฌ์šฉํ–ˆ์„ ๋•Œ๋„ ์ž˜ ํ’€๋ฆฌ๊ธด ํ•ฉ๋‹ˆ๋‹ค.

 

Java์˜ Integer ํด๋ž˜์Šค์—๋Š” toString ๋ฉ”์„œ๋“œ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•ด๋‹น ๋ฉ”์„œ๋“œ๋ฅผ ์ด์šฉํ•˜๋ฉด StringBuilder๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ ๋„ ์‰ฝ๊ฒŒ ์ˆซ์ž๋ฅผ ํŠน์ • ์ง„๋ฒ• ๊ฐ’์œผ๋กœ ๋ฐ”๊ฟ€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. 

 

 

 

Question 03 ์ฃผ์ฐจ ์š”๊ธˆ ๊ณ„์‚ฐ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92341)

 

์ฃผ์ฐจ์žฅ์˜ ์š”๊ธˆํ‘œ์™€ ์ฐจ๋Ÿ‰์ด ๋“ค์–ด์˜ค๊ณ (์ž…์ฐจ) ๋‚˜๊ฐ„(์ถœ์ฐจ) ๊ธฐ๋ก์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฐจ๋Ÿ‰๋ณ„๋กœ ์ฃผ์ฐจ ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•œ ํŠน์ • ์กฐ๊ฑด์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ฐจ๋Ÿ‰๋ฒˆํ˜ธ๊ฐ€ ์ž‘์€ ์ž๋™์ฐจ๋ถ€ํ„ฐ ์ฒญ๊ตฌํ•  ์ฃผ์ฐจ ์š”๊ธˆ์„ ์ฐจ๋ก€๋Œ€๋กœ ์ •์ˆ˜ ๋ฐฐ์—ด์— ๋‹ด์•„ return ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 03

๊ฐœ์ธ์ ์œผ๋กœ 3๋ฒˆ ๋ฌธ์ œ๋ณด๋‹ค๋Š” 2๋ฒˆ ๋ฌธ์ œ๊ฐ€ ๋” ์‰ฌ์› ๋˜ ๊ฒƒ ๊ฐ™์•˜๋Š”๋ฐ์š”. ์ •๋‹ต๋ฅ ์€ 73%๋กœ 2๋ฒˆ ๋ฌธ์ œ ์ •๋‹ต๋ฅ ์ธ 55%๋ณด๋‹ค ๋” ๋†’์€ ์ˆ˜์น˜์ž…๋‹ˆ๋‹ค. 3๋ฒˆ ๋ฌธ์ œ๊ฐ€ 2๋ฒˆ ๋ฌธ์ œ๋ณด๋‹ค ๊ฐœ์ธ์ ์œผ๋กœ ๋” ์–ด๋ ต๋‹ค๊ณ  ๋Š๊ปด์ง„ ๊ฒƒ์€ ๋ณต์žกํ•œ ์š”๊ตฌ์‚ฌํ•ญ ๋•Œ๋ฌธ์ด์—ˆ๋Š”๋ฐ์š”. ๊ฐ„๋‹จํ•˜๊ฒŒ ํ’€๋ ค๊ณ  ์ ‘๊ทผํ•˜๊ฒŒ ๋˜๋ฉด ์‹คํŒจ ์ผ€์ด์Šค๊ฐ€ ๋งŽ์ด ๋‚˜์˜ค๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

์ด ๋ฌธ์ œ๋ฅผ ํ’€๊ธฐ ์œ„ํ•ด์„œ๋Š” ๋จผ์ € ์ž…๋ ฅ์— ์ฃผ์–ด์ง„ ์‹œ๊ฐ„์„ ์ •์ˆ˜ ํƒ€์ž…์ธ int๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ๋ž˜์•ผ๋งŒ ์ž…์ฐจ์™€ ์ถœ์ฐจ๋ฅผ ๋น„๊ตํ•˜์—ฌ ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์ž…๋‹ˆ๋‹ค.

 

๊ทธ๋Ÿฐ ๋‹ค์Œ, ๊ฐ ์ฐจ๋Ÿ‰์˜ ์ฃผ์ฐจ ์‹œ๊ฐ„์„ ๋ชจ๋‘ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ๊ธฐ๋ณธ ์‹œ๊ฐ„์˜ ๊ฒฝ์šฐ ๊ธฐ๋ณธ ์‹œ๊ฐ„์„ ์ค€์ˆ˜ํ•˜๊ณ , ๊ทธ ์™ธ์—๋Š” ์š”๊ตฌ์‚ฌํ•ญ๋Œ€๋กœ ์ง„ํ–‰ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

๋งˆ์ง€๋ง‰์œผ๋กœ ์ฃผ์ฐจ ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค. ์ด ๋•Œ, ๋‹จ์œ„ ์‹œ๊ฐ„๋ณด๋‹ค ๋ฏธ๋งŒ์˜ ๊ณ„์‚ฐ์ด ๋‚˜์˜ค๋Š” ๊ฒฝ์šฐ์˜ ์ฒ˜๋ฆฌ๊ฐ€ ์ค‘์š”ํ•œ๋ฐ์š”. ์ด ๋ถ€๋ถ„์„ ์ž˜๋ชป ์ฒ˜๋ฆฌํ•˜๋ฉด ๋‹จ์œ„ ์‹œ๊ฐ„ ๋ฏธ๋งŒ์˜ ์š”๊ธˆ์— ๋Œ€ํ•ด์„œ ์ถ”๊ฐ€ ์š”๊ธˆ์ด ๊ณ„์‚ฐ๋˜๋Š” ์˜ค์ฐจ๊ฐ€ ๋‚˜์˜ค๊ธฐ ๋•Œ๋ฌธ์— ๋ฐ˜๋“œ์‹œ ์ด ๋ถ€๋ถ„ ์ฒ˜๋ฆฌํ•˜๋Š” ๋กœ์ง์„ ๋„ฃ์–ด์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค.

 

 

 

Question 04 ์–‘๊ถ ๋Œ€ํšŒ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92342)

 

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

 

์ด ๋•Œ, ๋ผ์ด์–ธ์ด ์–ดํ”ผ์น˜๋ฅผ ๊ฐ€์žฅ ํฐ ์ ์ˆ˜์ฐจ๋กœ ์ด๊ธฐ๊ธฐ ์œ„ํ•ด n๋ฐœ์˜ ํ™”์‚ด์„ ์–ด๋–ค ๊ณผ๋… ์ ์ˆ˜์— ๋งž์ถฐ์•ผ ํ•˜๋Š”์ง€๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 04

4๋ฒˆ ๋ฌธ์ œ๋ถ€ํ„ฐ ๋‚œ์ด๋„๊ฐ€ ์–ด๋ ค์›Œ์ง‘๋‹ˆ๋‹ค. ์ด ๋•Œ๋ถ€ํ„ฐ ์ •๋‹ต๋ฅ ์ด 21%๋กœ ๋‚ด๋ ค๊ฐ€๋Š”๋ฐ์š”. 

์ด ๋ฌธ์ œ๋Š” DFS๋ฅผ ์ด์šฉํ•˜์—ฌ ํ’€์–ด ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๊ฐ์ž ๊ตฌํ•œ ์ ์ˆ˜ํ‘œ ์ค‘์—์„œ ๊ฐ€์žฅ ํฐ ์ ์ˆ˜์ฐจ๊ฐ€ ๋‚˜๋Š” ์ ์ˆ˜๋ฅผ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์ ์ˆ˜ ํ…Œ์ด๋ธ”์„ ์ €์žฅํ•˜๋Š” ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“ค๊ณ , Java์˜ Comparable ์ธํ„ฐํŽ˜์ด์Šค๋กœ ๊ตฌํ˜„ํ•ฉ๋‹ˆ๋‹ค. ํ•ด๋‹น ์ธํ„ฐํŽ˜์ด์Šค๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ์ด์œ ๋Š” Java ์–ธ์–ด์—์„œ ์ œ๊ณตํ•˜๋Š” Sort ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ด์šฉํ•˜๊ธฐ ์œ„ํ•จ์ž…๋‹ˆ๋‹ค.

 

ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ ์กฐ๊ฑด์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ์ค‘๋ณต ์กฐ๊ฑด์„ ํˆฌ์—ฌํ•ด๋„ ์ข‹์„ ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ค‘๋ณต ์กฐ๊ฑด์ด๋ž€, visited์™€ ๊ฐ™์€ ์ค‘๋ณต ํŒ๋ณ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์—†์ด ์ค‘๋ณต ์กฐ๊ฑด์„ ์ˆ˜์šฉํ•ด ๊ทธ๋“ค ๋ฐ์ดํ„ฐ ์ค‘ ๊ฐ€์žฅ ๋†’์€ ์ ์ˆ˜๋ฅผ ํŒ๋ณ„ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

 

ํŠน์ • ์–ธ์–ด๋ฅผ ๊นŠ๊ฒŒ ์‘์šฉํ•˜๊ณ  ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•œ ์ง€์‹์ด ์–ด๋Š ์ •๋„ ๋˜๋Š”์ง€๋ฅผ ๋ณผ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค.

 

 

 

Question 05 ์–‘๊ณผ ๋Š‘๋Œ€

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92343)

 

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

 

์ด ๋•Œ, ์ œ์‹œํ•œ ์กฐ๊ฑด์— ๋”ฐ๋ผ ๊ฐ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ๋ชจ์„ ์ˆ˜ ์žˆ๋Š” ์–‘์€ ์ตœ๋Œ€ ๋ช‡ ๋งˆ๋ฆฌ์ธ์ง€ ๊ตฌํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 05

์ด ๋ฌธ์ œ๋„ 4๋ฒˆ ๋ฌธ์ œ์ฒ˜๋Ÿผ DFS๋ฅผ ์ด์šฉํ•ด ๋ฌธ์ œ๋ฅผ ํ’€์–ด๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๋จผ์ € ๊ฐ ๋…ธ๋“œ์˜ ์ง‘ํ•ฉ์„ Edge๋กœ ํ‘œํ˜„ํ•˜๊ณ , ๊ทธ๋“ค์ด ์–ด๋–ป๊ฒŒ ์ด์–ด์ ธ ์žˆ๋Š”์ง€์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ Graph๋กœ ํ‘œํ˜„ํ•˜์˜€์Šต๋‹ˆ๋‹ค. ์ด ๋ถ€๋ถ„์€ ์—ฌ๋Ÿฌ๋ถ„๋“ค์ด ํŽธํ•˜์‹ ๋Œ€๋กœ ๊ตฌํ˜„ํ•˜์‹œ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

์ค‘์š”ํ•œ ๊ฒƒ์€ DFS ๋ถ€๋ถ„์ž…๋‹ˆ๋‹ค. ์‚ฌ์‹ค ์œ„ ์ฝ”๋“œ๋Š” ํŠธ๋ฆฌ์˜ ๊ฐ ๋…ธ๋“œ์—์„œ ํ•œ ๋ฒˆ์”ฉ๋งŒ ๋ฐฉ๋ฌธํ•˜๊ณ  ๋๋‚˜๊ธฐ ๋•Œ๋ฌธ์— ์–‘์„ ์ตœ๋Œ€๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š” ๋งˆ๋ฆฟ์ˆ˜๋ฅผ ๊ตฌํ•œ๋‹ค๊ธฐ ๋ณด๋‹ค๋Š” ๊ฐ ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•ด์„œ ์˜ค๋ฅธ์ชฝ๊ณผ ์™ผ์ชฝ ์—ฌ๋ถ€ ์ƒ๊ด€์—†์ด ๋ฐฉ๋ฌธ๋งŒ ํ•˜๋ฉด ๋๋‚˜๊ธฐ ๋•Œ๋ฌธ์— max ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ–ˆ๋‹ค ํ•˜๋”๋ผ๋„ ์ •ํ™•ํ•˜๊ฒŒ ์ตœ๋Œ€ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š” ์–‘์˜ ๋งˆ๋ฆฟ์ˆ˜๋ฅผ ๊ตฌํ•  ์ˆ˜๊ฐ€ ์—†์Šต๋‹ˆ๋‹ค.

 

๋”ฐ๋ผ์„œ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ํŠธ๋ฆฌ์˜ ๋…ธ๋“œ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ณ , ํ•ด๋‹น ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋Š” ํ˜•ํƒœ๋กœ ์ž‘์„ฑํ•˜๊ณ , ๊ทธ ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ํƒ์ƒ‰ํ•  ๋•Œ ๋˜ ๋‹ค์‹œ ๊ทธ ๋…ธ๋“œ๋ฅผ ์ค‘๋ณต ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๋„๋ก ์œ ๋„ํ•˜์—ฌ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ๋ชจ๋“  ๋ฐฉ๋ฌธ ํ˜•ํƒœ๋ฅผ ๊ฐ€์ง€๊ธฐ ๋•Œ๋ฌธ์— ๋ณ„๋„์˜ max ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜์ง€ ์•Š๊ณ ๋„ ์ตœ๋Œ€๋กœ ๊ตฌํ•  ์ˆ˜ ์žˆ๋Š” ์–‘์˜ ๋งˆ๋ฆฟ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•ด๋‚ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

Question 06 ํŒŒ๊ดด๋˜์ง€ ์•Š์€ ๊ฑด๋ฌผ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92344)

 

N x M ํฌ๊ธฐ์˜ ํ–‰๋ ฌ ๋ชจ์–‘์˜ ๊ฒŒ์ž„ ๋งต์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๋งต์—๋Š” ๋‚ด๊ตฌ๋„๋ฅผ ๊ฐ€์ง„ ๊ฑด๋ฌผ์ด ๊ฐ ์นธ๋งˆ๋‹ค ํ•˜๋‚˜์”ฉ ์žˆ์Šต๋‹ˆ๋‹ค. ์ ์€ ์ด ๊ฑด๋ฌผ๋“ค์„ ๊ณต๊ฒฉํ•˜์—ฌ ํŒŒ๊ดดํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ฑด๋ฌผ์€ ์ ์˜ ๊ณต๊ฒฉ์„ ๋ฐ›์œผ๋ฉด ๋‚ด๊ตฌ๋„๊ฐ€ ๊ฐ์†Œํ•˜๊ณ  ๋‚ด๊ตฌ๋„๊ฐ€ 0์ดํ•˜๊ฐ€ ๋˜๋ฉด ํŒŒ๊ดด๋ฉ๋‹ˆ๋‹ค. ๋ฐ˜๋Œ€๋กœ, ์•„๊ตฐ์€ ํšŒ๋ณต ์Šคํ‚ฌ์„ ์‚ฌ์šฉํ•˜์—ฌ ๊ฑด๋ฌผ๋“ค์˜ ๋‚ด๊ตฌ๋„๋ฅผ ๋†’์ด๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

 

์ ์˜ ๊ณต๊ฒฉ ํ˜น์€ ์•„๊ตฐ์˜ ํšŒ๋ณต ์Šคํ‚ฌ์ด ๋ชจ๋‘ ๋๋‚œ ๋’ค ํŒŒ๊ดด๋˜์ง€ ์•Š์€ ๊ฑด๋ฌผ์˜ ๊ฐฏ์ˆ˜๊ฐ€ ๋ช‡ ๊ฐœ ์ธ์ง€๋ฅผ ์•Œ๋ ค์ฃผ๋Š” ํ•จ์ˆ˜๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 06

์˜ฌํ•ด ์นด์นด์˜ค ์‹ ์ž… ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ ํšจ์œจ์„ฑ์„ ์š”๊ตฌํ•˜๋Š” ์œ ์ผํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์–ธ๋œป ๋ณด๋ฉด ์™„์ „ ํƒ์ƒ‰์œผ๋กœ๋„ ์‰ฝ๊ฒŒ ๊ฐ€๋Šฅํ•ด ๋ณด์ด์ง€๋งŒ ํšจ์œจ์„ฑ์ด ๊ฑธ๋ ค ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ์™„์ „ ํƒ์ƒ‰์ธ O(N * M)์œผ๋กœ ํ’€์ด๋ฅผ ํ•˜๊ฒŒ ๋˜๋ฉด ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ์— ์‰ฝ๊ฒŒ ๋ง๊ฐ€์งˆ ์ˆ˜ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

์Šคํ‚ฌ์ด ๊ณต๊ฒฉ ์Šคํ‚ฌ์ธ์ง€ ํšŒ๋ณต ์Šคํ‚ฌ์ธ์ง€๋ฅผ ํ™•์ธํ•˜๊ณ , Dynamic Programming ๊ธฐ๋ฒ•์„ ํ†ตํ•ด ํ•ด๋‹น ์Šคํ‚ฌ์ด ๋ฐœ๋™๋˜๊ณ  ๋‚œ ํ›„์˜ matrix๋ฅผ ๊ณ„์‚ฐํ•ฉ๋‹ˆ๋‹ค.

์ด๋ ‡๊ฒŒ ๋ˆ„์ ํ•ฉ์ด ์ ์šฉ๋œ ์ƒํƒœ๋กœ matrix๋ฅผ ์™„์ „ ํƒ์ƒ‰ํ•˜์—ฌ ํŒŒ๊ดด๋˜์ง€ ์•Š์€ ๊ฑด๋ฌผ์„ ์Šค์บ”ํ•˜๋ฉด ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ์—์„œ ํ†ต๊ณผ๋ฅผ ํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. (์‹œ๊ฐ„๋ณต์žก๋„: O(N * M * K) )

 

์ด ๋ฌธ์ œ ํ’€์ด์˜ ํ•ต์‹ฌ์€ ์ขŒ -> ์šฐ, ์ƒ -> ํ•˜๋กœ ๋ˆ„์ ํ•ฉ์„ ์ง„ํ–‰ํ•˜์—ฌ O(K)๊ฐ€ ๋˜๋Š” ์ž‘์—…์„ O(1)๋กœ ์ตœ์ ํ™”ํ•˜๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค. ์ด๋ ‡๊ฒŒ๋งŒ ํ•˜๋ฉด O(N * M * K)๊ฐ€ O(N * M + K)๋กœ ์ตœ์ ํ™” ๋˜๊ธฐ ๋•Œ๋ฌธ์— ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ๋ฅผ ์‰ฝ๊ฒŒ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

 

 

Question 07 ์‚ฌ๋ผ์ง€๋Š” ๋ฒŒํŒ

๋ฌธ์ œ ์›๋ฌธ: (https://programmers.co.kr/learn/courses/30/lessons/92345)

 

ํ”Œ๋ ˆ์ด์–ด A์™€ ํ”Œ๋ ˆ์ด์–ด B๊ฐ€ ์„œ๋กœ ๊ฒŒ์ž„์„ ํ•ฉ๋‹ˆ๋‹ค. ๋‹น์‹ ์€ ์ด ๊ฒŒ์ž„์ด ๋๋‚  ๋•Œ๊นŒ์ง€ ์–‘ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์บ๋ฆญํ„ฐ๋ฅผ ๋ช‡ ๋ฒˆ ์›€์ง์ด๊ฒŒ ๋ ์ง€ ์˜ˆ์ธกํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. 

๊ฐ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ 1x1 ๊ฒŒ์ž„ ๋ณด๋“œ์—์„œ ํŠน์ • ์กฐ๊ฑด์œผ๋กœ ๊ฒŒ์ž„์„ ์ˆ˜ํ–‰ํ–ˆ์„ ๋•Œ, ๋‘ ์บ๋ฆญํ„ฐ๊ฐ€ ์ตœ์ ์˜ ํ”Œ๋ ˆ์ด๋กœ ์›€์ง์ธ ํšŸ์ˆ˜์˜ ํ•ฉ์„ ๊ตฌํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

 

 

Solution for Question 07

์—ญ๋Œ€ ์นด์นด์˜ค ์‹ ์ž… ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋งˆ์ง€๋ง‰ ๋ฌธ์ œ์ธ ๊ฒƒ์น˜๊ณค, ์‰ฌ์šด ์กฐ๊ฑด์œผ๋กœ ์ถœ์ œ๋œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ณด๋“œ๊ฐ€ ์ผ๋‹จ ํฌ์ง€ ์•Š๊ณ , ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ง€๋‚˜๊ฐ€๋ฉด ๋‹จ์ˆœํžˆ ๊ทธ ๋ณด๋“œ์— ์žˆ๋Š” ํŒ์ด ์‚ฌ๋ผ์ง„๋‹ค๋Š” ์กฐ๊ฑด์ด๊ธฐ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ํƒ์ƒ‰ ์กฐ๊ฑด์ด ์ค„์–ด๋“ญ๋‹ˆ๋‹ค. ๋”ฐ๋ผ์„œ ์ด ๋ฌธ์ œ๋Š” DFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์จ์„œ ์ถฉ๋ถ„ํžˆ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

 

๋งคํŒ ํ”Œ๋ ˆ์ด์–ด์˜ ์ŠนํŒจ ์—ฌ๋ถ€์™€ ์›€์ง์ธ ํšŸ์ˆ˜๋ฅผ ํ™•์ธํ•˜๋Š” ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“ญ๋‹ˆ๋‹ค. ์‹œ์ž‘ ์ง€์ ์—์„œ ๋ˆ„๊ตฐ๊ฐ€ ๊ฒŒ์ž„์—์„œ ์ด๊ธด ๊ฒฝ์šฐ, ์ด ๊ฒŒ์ž„์€ ๋น ๋ฅด๊ฒŒ ์ข…๋ฃŒ๋˜๋ฉฐ ์ตœ์†Œ ์›€์ง์ธ ํšŸ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

๋ฐ˜๋Œ€๋กœ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ๋จผ์ € ์ง€๋Š” ์ผ€์ด์Šค๊ฐ€ ๋ฐœ์ƒํ•˜๋Š” ๊ฒฝ์šฐ, ์ง„ ํ”Œ๋ ˆ์ด์–ด๊ฐ€ ์ด๋™ํ•œ ํšŸ์ˆ˜ ๋“ฑ์„ ๋ˆ„์ ํ•œ ์ƒํƒœ๋กœ ๋ฐ˜ํ™˜ํ•ด์ฃผ๋ฉด ๋ฉ๋‹ˆ๋‹ค.

 

 

 

๋งˆ์น˜๋ฉฐ...

์ž‘๋…„ ๋ฌธ์ œ์™€ ๋น„๊ตํ•ด๋ดค์„ ๋•Œ, 2022๋…„ ์นด์นด์˜ค ์‹ ์ž… 1์ฐจ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ๋Š” ๋‚œ์ด๋„๊ฐ€ ๋งŽ์ด ๋‚ฎ์•„์ง„ ๋ชจ์Šต์ž…๋‹ˆ๋‹ค. ํ•„์š” ์ด์ƒ์˜ ๋‚œ์ด๋„๊ฐ€ ๋†’์€ ๋ฌธ์ œ ์ถœ์ œ ๋น„์ค‘์„ ์ค„์ด๊ณ , ๊ธฐ๋ณธ์ ์ธ ๋ฌธ์ œ(Lv 1 ~ Lv 2) ์ˆ˜์ค€์˜ ๋ฌธ์ œ๋ฅผ ๋งŽ์ด ์ถœ์ œํ•œ ๋’ค, ํ•ด๋‹น ๋ฌธ์ œ์—์„œ ํšจ์œจ์„ฑ ๋“ฑ์„ ์ถ”๊ฐ€ํ•ด ๋ณ€๋ณ„๋ ฅ์„ ์คŒ์œผ๋กœ์จ ํ™•์‹คํ•˜๊ฒŒ ์–ด๋–ค ์ง€์›์ž๋ฅผ ๋ฝ‘์œผ๋ ค ํ•˜๋Š”์ง€๋ฅผ ๋งฅ๋ฝ์ด ์˜ฌํ•ด๋Š” ์œ ๋‚œํžˆ ์ž˜ ๋ณด์˜€๋˜ ๋ฌธ์ œ๋“ค์ด์—ˆ๋‹ค๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค.

 

 

์ฐธ๊ณ : 2022 ์นด์นด์˜ค ์‹ ์ž… ๊ณต์ฑ„ 1์ฐจ ์˜จ๋ผ์ธ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ for Tech developers ๋ฌธ์ œ ํ•ด์„ค

(https://tech.kakao.com/2022/01/14/2022-kakao-recruitment-round-1/)

 

๋ฐ˜์‘ํ˜•
TAGS.

Tistory Comments