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

[Level 1] ๋ฌธ์ž์—ด ๋‚ด ๋งˆ์Œ๋Œ€๋กœ ์ •๋ ฌํ•˜๊ธฐ

by ๐Ÿ‡๋ฐ•๋ด‰๋ด‰๐Ÿ‡ 2021. 4. 27.

 

 

 

Algorithm

-  ๋ฌธ์ž์—ด ๋‚ด ๋งˆ์Œ๋Œ€๋กœ ์ •๋ ฌํ•˜๊ธฐ -

 


 

๋ฌธ์ œ

๋ฌธ์ž์—ด๋กœ ๊ตฌ์„ฑ๋œ ๋ฆฌ์ŠคํŠธ strings์™€, ์ •์ˆ˜ n์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ๊ฐ ๋ฌธ์ž์—ด์˜ ์ธ๋ฑ์Šค n๋ฒˆ์งธ ๊ธ€์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด strings๊ฐ€ ["sun", "bed", "car"]์ด๊ณ  n์ด 1์ด๋ฉด ๊ฐ ๋‹จ์–ด์˜ ์ธ๋ฑ์Šค 1์˜ ๋ฌธ์ž "u", "e", "a"๋กœ strings๋ฅผ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค.

 

- ์ธ๋ฑ์Šค 1์˜ ๋ฌธ์ž๊ฐ€ ๊ฐ™์€ ๋ฌธ์ž์—ด์ด ์—ฌ๋Ÿฟ์ผ ๊ฒฝ์šฐ, ์‚ฌ์ „์ˆœ์œผ๋กœ ์•ž์„  ๋ฌธ์ž์—ด์ด ์•ž์ชฝ์— ์œ„์น˜ํ•ฉ๋‹ˆ๋‹ค.

 

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

numbers result
[2, 1, 3, 4, 1] [2, 3, 4, 5, 6, 7]
[5, 0, 2, 7] [2, 5, 7, 9, 12]

 

๋ฌธ์ œ ํ’€๊ธฐ

 

์ด๋ฒˆ ๋ฌธ์ œ๋Š” ํ•œ์ค„์„ ํ•˜๋‚˜ ํ•œ์จ์„œ ์กฐ๊ธˆ ํ—ค๋งธ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

 

์ผ๋‹จ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ๋ฐฐ์—ด๊ณผ ์ˆซ์ž๋ฅผ ๋ฐ›์„ ๊ฒฝ์šฐ ๋ฐ›์€ ์ˆซ์ž๋ฅผ ๋ฐฐ์—ด์•ˆ์— ๊ฐ ๋ฌธ์ž์—ด์˜ n๋ฒˆ์งธ์˜ ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ฆฌ๋ฅผ ์ง„ํ–‰ํ•˜๋Š” ๋ฌธ์ œ์˜€๋Š”๋ฐ ์ด๋•Œ n๋ฒˆ์งธ์— ์žˆ๋Š” ๊ฐ’์ด ๊ฐ™์„ ๊ฒฝ์šฐ์—” ์‚ฌ์ „์ˆœ์œผ๋กœ ์•ž์„  ๋ฌธ์ž์—ด์ด ์•ž์ชฝ์— ์œ„์น˜ํ•˜๋„๋ก ์ง„ํ–‰ํ•˜๋ฉด ๋œ๋‹ค.

 

๊ทธ๋ž˜์„œ ๋‚˜๋Š” ์ผ๋‹จ ์ฝ”๋“œ๋ฅผ ๋ณธ๊ฒฉ์ ์œผ๋กœ ํ’€์–ด๋‚˜๊ฐ€๊ธฐ ์ „์— ์ธ๋ฑ์Šค์— ๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์žˆ์„ ๊ฒฝ์šฐ์—” ๋‹ค๋ฅธ ์•ŒํŒŒ๋ฒณ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌ์„ ์–ด์จ‹๋“  ์ง„ํ–‰ํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฐฐ์—ด์„ ์ผ๋‹จ sort()๋ฅผ ์ง„ํ–‰ํ•ด ์˜ค๋ฆ„์ฐจ์ˆœ์„ ์ง„ํ–‰ํ•ด ์ฃผ์—ˆ๋‹ค.

(์ด๋ ‡๊ฒŒ ํ•˜๋ฉด ์กฐ๊ฑด๋ฌธ์„ ๋”ฐ๋กœ ๋‹ฌ์•„์„œ ๋ฌธ์ œ๋ฅผ ์–ด๋ ต๊ฒŒ ํ•ด๊ฒฐํ•ด ๋‚˜๊ฐ€์ง€ ์•Š์•„๋„ ๋œ๋‹ค.)

 

๊ทธ ์ดํ›„์—” strings์•ˆ์— ์žˆ๋Š” ๊ฐ ๋ฐฐ์—ด์•ˆ์— ์žˆ๋Š” ๋ฌธ์ž์—ด๋“ค์—์„œ n๋ฒˆ์งธ์— ์žˆ๋Š” ๊ฐ’์ด ์–ด๋–ค ๊ฒƒ์ธ์ง€์— ๋Œ€ํ•ด ๋”ฐ๋กœ ๋‹ด์•„๋‚ด๋Š” ๋ณ€์ˆ˜ indexAlpha๋ฅผ ๋งŒ๋“ค์—ˆ๋‹ค.

 

์ดํ›„์—” ์ด์ค‘ ๋ฐ˜๋ณต๋ฌธ์„ ์‚ฌ์šฉํ•ด์„œ indexAlpha๋งŒํผ ๋Œ๋ฆฌ๋ฉด์„œ strings๋ฐฐ์—ด์•ˆ์— ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ๊ฐ’๊ณผ ์ผ์น˜ํ•˜๋Š” ๊ฐ’์ด ์žˆ์œผ๋ฉด ๋ฐ”๋กœ ๋„ฃ์„ ์ˆ˜ ์žˆ๋„๋ก ์ง„ํ–‰์‹œ์ผฐ๋‹ค.

 

๊ทธ๋Ÿฐ๋ฐ ์ด๋•Œ ๋ฌธ์ œ์ ์€ ๋„ฃ๊ณ ๋‚˜์„œ ๋์„ ๋‚ด๋ฒ„๋ฆฌ๋ฉด ๋งŒ์•ฝ ์ธ๋ฑ์Šค์— ๊ฐ™์€ ๋ฌธ์ž๊ฐ€ ์žˆ๋Š” ๋ฌธ์ž์—ด์ด ์—ฌ๋Ÿฌ๊ฐœ์ผ ๊ฒฝ์šฐ์— ๋ฐ˜๋ณต์ ์œผ๋กœ ํ•œ ๊ฐœ์˜ ๋ฌธ์ž๋งŒ ๋ฐ˜๋ณต๋ฌธ์— ๊ฑธ๋ ค์„œ ๋‹ค๋ฅธ ๋ฌธ์ž๋“ค์ด ๋‚˜์˜ค์ง€ ์•Š์„ ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— result์— ๊ฐ’์„ ๋„ฃ์–ด์ค€ ๋‹ค์Œ์— ๋ฐ”๋กœ arr์˜ ๊ฐ’์„ ๋นˆ ๊ฐ’์„ ๋„ฃ์–ด์ฃผ์—ˆ๋‹ค.

 

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

 

๊ทธ๋ž˜์„œ arr์˜ ๊ฐ’์„ ๋นˆ ๊ฐ’์œผ๋กœ ๋„ฃ์–ด์ค€ ๋‹ค์Œ์—๋Š” ์ผ์„ ์ฒ˜๋ฆฌํ•œ ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋”์ด์ƒ ๋ฐ˜๋ณต๋ฌธ์ด ๋Œ์•„๊ฐ€์ง€ ์•Š๋„๋ก break๋ฅผ ๊ฑธ์–ด์ฃผ์—ˆ๋”๋‹ˆ ๋ฌธ์ œ๊ฐ€ ์ž์—ฐ์Šค๋Ÿฝ๊ฒŒ ํ•ด๊ฒฐ๋˜๋Š” ๊ฒƒ์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

 

 

๋ฐ˜์‘ํ˜•

๋Œ“๊ธ€