Algorithm/ํŒŒ์ด์ฌ ์ฝ”๋”ฉํ…Œ์ŠคํŠธ

์ฝ”๋“œ ๊ตฌํ˜„๋ ฅ ๊ธฐ๋ฅด๊ธฐ / 1. K๋ฒˆ์งธ ์•ฝ์ˆ˜

hello_u 2023. 1. 3. 16:03




๋‚˜์˜ ํ’€์ด

์ž์—ฐ์ˆ˜ N , K ๋ฅผ ์ž…๋ ฅ๋ฐ›๋Š”๋‹ค
1๋ถ€ํ„ฐ ์ž์—ฐ์ˆ˜ N๊นŒ์ง€ ๋ฐ˜๋ณต๋ฌธ์„ ์‹คํ–‰
N์„ ์ฐจ๋ก€๋กœ ๋‚˜๋ˆ ๊ฐ€๋ฉฐ ๋‚˜๋จธ์ง€๊ฐ€ 0์ด ๋˜๋Š” N์„ ์ฐพ๋Š”๋‹ค -> ์ด๊ฒƒ๋“ค์€ N์˜ ์•ฝ์ˆ˜๋“ค์ด๊ฒ ์ง€ ?
๋ฐ˜๋ณต๋ฌธ์˜ ์‹คํ–‰์œผ๋กœ ๋‚˜์˜จ N์˜ ๊ฐ’๋“ค์„ ๋ฐฐ์—ด์— ์ €์žฅํ•œ๋‹ค
๋ฐฐ์—ด[K-1] ๋ฅผ ์ถœ๋ ฅํ•˜์ž
N์˜ ์•ฝ์ˆ˜๋“ค์˜ ๊ฐœ์ˆ˜ = ๋ฐฐ์—ด์˜ ๊ธธ์ด : len(arr) < K ์ผ๋•Œ -1 ์„ ์ถœ๋ ฅ





๊ฐ•์˜๋ฅผ ๋“ฃ๊ณ  ์„ ์ƒ๋‹˜์˜ ํ’€์ด๋ฅผ ๋ณด๋„๋ก ํ•ด๋ณด์ž

โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”โ€”
์นด์šดํ„ฐ๋ฅผ ์ถ”๊ฐ€ ( ์•ฝ์ˆ˜๋ฅผ ์ฐพ์•˜์„๋•Œ ์นด์šดํ„ฐ๋ฅผ ์ฆ๊ฐ€ ) /
โ€”> i ๋ฐ˜๋ณต -> ์•ฝ์ˆ˜ ์ฐพ์Œ -> cnt 1์ฆ๊ฐ€ -> cnt ์™€ k ๊ฐ’ ํ™•์ธ -> ๊ฐ™๋‹ค๋ฉด break
K : N์˜ ์•ฝ์ˆ˜๋“ค์ค‘ K ๋ฒˆ์งธ๋กœ ์ž‘์€ ์ˆ˜

break : ์•ฝ์ˆ˜๋“ค์ค‘์—์„œ k ๋ฒˆ์งธ๋กœ ์ž‘์€ ์ˆ˜๋ฅผ ์ฐพ์•˜๋‹ค๋ฉด ๋ฐ˜๋ณต๋ฌธ์„ ๋น ์ ธ๋‚˜์˜จ๋‹ค

for else :
์ด๊ฒŒ break๋ฌธ์ด ๊ฑธ๋ ค์„œ ๋น ์ ธ๋‚˜๊ฐ€๋Š”์ง€ ์•„๋‹Œ์ง€๋ฅผ ํŒ๋‹จ์ด ํ•„์š”ํ•œ ๊ฒฝ์šฐ
for ๊ฐ€ break์—†์ด ๋น ์ ธ๋‚˜์˜ฌ๊ฒฝ์šฐ -1 ์ด ์ถœ๋ ฅ์ด ๋œ๋‹ค.
k๋ฒˆ์งธ ์•ฝ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ -1 ์ถœ๋ ฅ