๐โโ๏ธ[ํ๋ก๊ทธ๋๋จธ์ค] ์ง๊ฒ๋ค๋ฆฌ ๊ฑด๋๊ธฐ
๋ฌธ์ ์ค๋ช
[๋ณธ ๋ฌธ์ ๋ ์ ํ์ฑ๊ณผ ํจ์จ์ฑ ํ ์คํธ ๊ฐ๊ฐ ์ ์๊ฐ ์๋ ๋ฌธ์ ์ ๋๋ค.]
์นด์นด์ค ์ด๋ฑํ๊ต์ "๋๋์ฆ ์น๊ตฌ๋ค"์ด "๋ผ์ด์ธ" ์ ์๋๊ณผ ํจ๊ป ๊ฐ์ ์ํ์ ๊ฐ๋ ์ค์ ์ง๊ฒ๋ค๋ฆฌ๊ฐ ์๋ ๊ฐ์ธ์ ๋ง๋์ ๊ฑด๋ํธ์ผ๋ก ๊ฑด๋๋ ค๊ณ ํฉ๋๋ค. "๋ผ์ด์ธ" ์ ์๋์ "๋๋์ฆ ์น๊ตฌ๋ค"์ด ๋ฌด์ฌํ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ์ ์๋๋ก ๋ค์๊ณผ ๊ฐ์ด ๊ท์น์ ๋ง๋ค์์ต๋๋ค.
- ์ง๊ฒ๋ค๋ฆฌ๋ ์ผ๋ ฌ๋ก ๋์ฌ ์๊ณ ๊ฐ ์ง๊ฒ๋ค๋ฆฌ์ ๋๋ค๋์๋ ๋ชจ๋ ์ซ์๊ฐ ์ ํ ์์ผ๋ฉฐ ๋๋ค๋์ ์ซ์๋ ํ ๋ฒ ๋ฐ์ ๋๋ง๋ค 1์ฉ ์ค์ด๋ญ๋๋ค.
- ๋๋ค๋์ ์ซ์๊ฐ 0์ด ๋๋ฉด ๋ ์ด์ ๋ฐ์ ์ ์์ผ๋ฉฐ ์ด๋๋ ๊ทธ ๋ค์ ๋๋ค๋๋ก ํ๋ฒ์ ์ฌ๋ฌ ์นธ์ ๊ฑด๋ ๋ธ ์ ์์ต๋๋ค.
- ๋จ, ๋ค์์ผ๋ก ๋ฐ์ ์ ์๋ ๋๋ค๋์ด ์ฌ๋ฌ ๊ฐ์ธ ๊ฒฝ์ฐ ๋ฌด์กฐ๊ฑด ๊ฐ์ฅ ๊ฐ๊น์ด ๋๋ค๋๋ก๋ง ๊ฑด๋๋ธ ์ ์์ต๋๋ค.
"๋๋์ฆ ์น๊ตฌ๋ค"์ ๊ฐ์ธ์ ์ผ์ชฝ์ ์์ผ๋ฉฐ, ๊ฐ์ธ์ ์ค๋ฅธ์ชฝ ๊ฑด๋ํธ์ ๋์ฐฉํด์ผ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ๊ฒ์ผ๋ก ์ธ์ ํฉ๋๋ค.
"๋๋์ฆ ์น๊ตฌ๋ค"์ ํ ๋ฒ์ ํ ๋ช ์ฉ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋์ผ ํ๋ฉฐ, ํ ์น๊ตฌ๊ฐ ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๋ชจ๋ ๊ฑด๋ ํ์ ๊ทธ ๋ค์ ์น๊ตฌ๊ฐ ๊ฑด๋๊ธฐ ์์ํฉ๋๋ค.
๋๋ค๋์ ์ ํ ์ซ์๊ฐ ์์๋๋ก ๋ด๊ธด ๋ฐฐ์ด stones์ ํ ๋ฒ์ ๊ฑด๋๋ธ ์ ์๋ ๋๋ค๋์ ์ต๋ ์นธ์ k๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์ต๋ ๋ช ๋ช ๊น์ง ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋ ์ ์๋์ง return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
[์ ํ์ฌํญ]
- ์ง๊ฒ๋ค๋ฆฌ๋ฅผ ๊ฑด๋์ผ ํ๋ ๋๋์ฆ ์น๊ตฌ๋ค์ ์๋ ๋ฌด์ ํ ์ด๋ผ๊ณ ๊ฐ์ฃผํฉ๋๋ค.
- stones ๋ฐฐ์ด์ ํฌ๊ธฐ๋ 1 ์ด์ 200,000 ์ดํ์ ๋๋ค.
- stones ๋ฐฐ์ด ๊ฐ ์์๋ค์ ๊ฐ์ 1 ์ด์ 200,000,000 ์ดํ์ธ ์์ฐ์์ ๋๋ค.
- k๋ 1 ์ด์ stones์ ๊ธธ์ด ์ดํ์ธ ์์ฐ์์ ๋๋ค.
[์ ์ถ๋ ฅ ์]
stones | k | result |
---|---|---|
[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] | 3 | 3 |
์ ์ถ๋ ฅ ์์ ๋ํ ์ค๋ช
์ ์ถ๋ ฅ ์ #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
}
Author And Source
์ด ๋ฌธ์ ์ ๊ดํ์ฌ(๐โโ๏ธ[ํ๋ก๊ทธ๋๋จธ์ค] ์ง๊ฒ๋ค๋ฆฌ ๊ฑด๋๊ธฐ), ์ฐ๋ฆฌ๋ ์ด๊ณณ์์ ๋ ๋ง์ ์๋ฃ๋ฅผ ๋ฐ๊ฒฌํ๊ณ ๋งํฌ๋ฅผ ํด๋ฆญํ์ฌ ๋ณด์๋ค https://velog.io/@kwb020312/ํ๋ก๊ทธ๋๋จธ์ค-์ง๊ฒ๋ค๋ฆฌ-๊ฑด๋๊ธฐ์ ์ ๊ท์: ์์์ ์ ๋ณด๊ฐ ์์์ URL์ ํฌํจ๋์ด ์์ผ๋ฉฐ ์ ์๊ถ์ ์์์ ์์ ์ ๋๋ค.
์ฐ์ํ ๊ฐ๋ฐ์ ์ฝํ ์ธ ๋ฐ๊ฒฌ์ ์ ๋ (Collection and Share based on the CC Protocol.)
์ข์ ์นํ์ด์ง ์ฆ๊ฒจ์ฐพ๊ธฐ
๊ฐ๋ฐ์ ์ฐ์ ์ฌ์ดํธ ์์ง
๊ฐ๋ฐ์๊ฐ ์์์ผ ํ ํ์ ์ฌ์ดํธ 100์ ์ถ์ฒ ์ฐ๋ฆฌ๋ ๋น์ ์ ์ํด 100๊ฐ์ ์์ฃผ ์ฌ์ฉํ๋ ๊ฐ๋ฐ์ ํ์ต ์ฌ์ดํธ๋ฅผ ์ ๋ฆฌํ์ต๋๋ค