๐Ÿƒโ€โ™€๏ธ[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ง•๊ฒ€๋‹ค๋ฆฌ ๊ฑด๋„ˆ๊ธฐ

๋ฌธ์ œ ์„ค๋ช…

[๋ณธ ๋ฌธ์ œ๋Š” ์ •ํ™•์„ฑ๊ณผ ํšจ์œจ์„ฑ ํ…Œ์ŠคํŠธ ๊ฐ๊ฐ ์ ์ˆ˜๊ฐ€ ์žˆ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.]

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

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

"๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค"์€ ๊ฐœ์šธ์˜ ์™ผ์ชฝ์— ์žˆ์œผ๋ฉฐ, ๊ฐœ์šธ์˜ ์˜ค๋ฅธ์ชฝ ๊ฑด๋„ˆํŽธ์— ๋„์ฐฉํ•ด์•ผ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„Œ ๊ฒƒ์œผ๋กœ ์ธ์ •ํ•ฉ๋‹ˆ๋‹ค.

"๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค"์€ ํ•œ ๋ฒˆ์— ํ•œ ๋ช…์”ฉ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ์•ผ ํ•˜๋ฉฐ, ํ•œ ์นœ๊ตฌ๊ฐ€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๋ชจ๋‘ ๊ฑด๋„Œ ํ›„์— ๊ทธ ๋‹ค์Œ ์นœ๊ตฌ๊ฐ€ ๊ฑด๋„ˆ๊ธฐ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค.

๋””๋”ค๋Œ์— ์ ํžŒ ์ˆซ์ž๊ฐ€ ์ˆœ์„œ๋Œ€๋กœ ๋‹ด๊ธด ๋ฐฐ์—ด stones์™€ ํ•œ ๋ฒˆ์— ๊ฑด๋„ˆ๋›ธ ์ˆ˜ ์žˆ๋Š” ๋””๋”ค๋Œ์˜ ์ตœ๋Œ€ ์นธ์ˆ˜ k๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ์ตœ๋Œ€ ๋ช‡ ๋ช…๊นŒ์ง€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ ์ˆ˜ ์žˆ๋Š”์ง€ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

[์ œํ•œ์‚ฌํ•ญ]

  • ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ์•ผ ํ•˜๋Š” ๋‹ˆ๋‹ˆ์ฆˆ ์นœ๊ตฌ๋“ค์˜ ์ˆ˜๋Š” ๋ฌด์ œํ•œ ์ด๋ผ๊ณ  ๊ฐ„์ฃผํ•ฉ๋‹ˆ๋‹ค.
  • stones ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๋Š” 1 ์ด์ƒ 200,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • stones ๋ฐฐ์—ด ๊ฐ ์›์†Œ๋“ค์˜ ๊ฐ’์€ 1 ์ด์ƒ 200,000,000 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.
  • k๋Š” 1 ์ด์ƒ stones์˜ ๊ธธ์ด ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

[์ž…์ถœ๋ ฅ ์˜ˆ]

stoneskresult
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]33

์ž…์ถœ๋ ฅ ์˜ˆ์— ๋Œ€ํ•œ ์„ค๋ช…


์ž…์ถœ๋ ฅ ์˜ˆ #1

์ฒซ ๋ฒˆ์งธ ์นœ๊ตฌ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ฒซ ๋ฒˆ์งธ ์นœ๊ตฌ๊ฐ€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„Œ ํ›„ ๋””๋”ค๋Œ์— ์ ํžŒ ์ˆซ์ž๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
๋‘ ๋ฒˆ์งธ ์นœ๊ตฌ๋„ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ์นœ๊ตฌ๊ฐ€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„Œ ํ›„ ๋””๋”ค๋Œ์— ์ ํžŒ ์ˆซ์ž๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
์„ธ ๋ฒˆ์งธ ์นœ๊ตฌ๋„ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์„ธ ๋ฒˆ์งธ ์นœ๊ตฌ๊ฐ€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„Œ ํ›„ ๋””๋”ค๋Œ์— ์ ํžŒ ์ˆซ์ž๋Š” ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.
๋„ค ๋ฒˆ์งธ ์นœ๊ตฌ๊ฐ€ ์ง•๊ฒ€๋‹ค๋ฆฌ๋ฅผ ๊ฑด๋„ˆ๋ ค๋ฉด, ์„ธ ๋ฒˆ์งธ ๋””๋”ค๋Œ์—์„œ ์ผ๊ณฑ ๋ฒˆ์งธ ๋””๋”ค๋Œ๋กœ ๋„ค ์นธ์„ ๊ฑด๋„ˆ๋›ฐ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ํ•˜์ง€๋งŒ k = 3 ์ด๋ฏ€๋กœ ๊ฑด๋„ˆ๋›ธ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๋”ฐ๋ผ์„œ ์ตœ๋Œ€ 3๋ช…์ด ๋””๋”ค๋Œ์„ ๋ชจ๋‘ ๊ฑด๋„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

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

์ด๋ถ„ํƒ์ƒ‰ ๋ฌธ์ œ์ธ๊ฑธ ๋ชจ๋ฅด๊ณ  ํ’€์—ˆ๋‹ค๊ฐ€ ํšจ์œจ์„ฑ์ด ๋ชจ๋‘ 0์ ์ฒ˜๋ฆฌ ๋˜์–ด ๊ต‰์žฅํžˆ ๋‹นํ™ฉ์Šค๋Ÿฌ์› ๋˜ ๋ฌธ์ œ์ด๋‹ค.

์งˆ๋ฌธํ•˜๊ธฐ๋ฅผ ํ†ตํ•ด ๋‹ค๋ฅธ๋ถ„๋“ค์˜ ์˜๊ฒฌ์„ ์‚ดํŽด๋ณด๋‹ˆ ๋ฒ”์œ„๊ฐ€ ๋งค์šฐ ๊ด‘๋ฒ”์œ„ํ•œ ๊ฒฝ์šฐ 99% ์ด๋ถ„ํƒ์ƒ‰ ๋ฌธ์ œ๋ผ๋Š” ๋ง์”€์„ ๋“ฃ๊ณ  ๋‚˜์„œ์•ผ ์ด๋ถ„ํƒ์ƒ‰์„ ๋ˆˆ์น˜์ฑ„๊ณ  ํ’€์—ˆ๋˜ ๊ฒƒ ๊ฐ™๋‹ค.

์ด๋ถ„ํƒ์ƒ‰์˜ min ์€ ๊ฐ€๋Šฅํ•œ ์ตœ๋Œ“๊ฐ’์„ ์˜๋ฏธํ•˜๊ณ  max ๋Š” ๊ฐ€๋Šฅํ•œ ์ตœ์†Ÿ๊ฐ’์„ ์˜๋ฏธํ•˜๊ธฐ์— ํ•ด๋‹น ๋ฌธ์ œ๋Š” min ์„ return ํ•ด์ฃผ๋ฉด ๋

function solution(stones, k) {
    // ๋ฌธ์ œ์— ๋ช…์‹œ๋œ ์ตœ์†Œ/์ตœ๋Œ“ ๊ฐ’
    let min = 1
    let max = 200000000
    while(min < max-1) {
        // >> 0 ์€ ๋‚˜๋จธ์ง€๋ฅผ ๋ฒ„๋ฆฌ๋Š” ๋น„ํŠธ ์—ฐ์‚ฐ์„ ๋งํ•จ
        const mid = (min+max)/2 >> 0
        let canJump = 0
        for(let i = 0 ; i < stones.length ; i ++) {
            // stones[i] < mid ๋Š” ํ•ด๋‹น ์ธ๋ฑ์Šค์˜ ๊ฐ’์ด 0๋ณด๋‹ค ์ž‘์Œ์„ ์˜๋ฏธ
            if(stones[i] < mid) canJump++
            else {canJump=0}
            // ์ ํ”„ํ•ด๋„ ๊ฑด๋„ˆ๊ฐ€์ง€ ๋ชปํ•˜๋ฉด
            if(canJump >= k) break
        }
        // ์ค‘๊ฐ„๊ฐ’์„ ์ตœ๋Œ“๊ฐ’์— ์‚ฝ์ž…
        if(canJump >= k) {max = mid;}
        else {min= mid;}
    }
    // ๊ฐ€๋Šฅํ•œ ์ตœ๋Œ“๊ฐ’
    return min
}

์ข‹์€ ์›นํŽ˜์ด์ง€ ์ฆ๊ฒจ์ฐพ๊ธฐ