๋ณธ ํฌ์ŠคํŠธ๋Š” ํ‹ฐ์Šคํ† ๋ฆฌ Vintz ๋‹˜์˜ [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]๋•…๋”ฐ๋จน๊ธฐ | JavaScript

๋ฌธ์ œ ์„ค๋ช…
๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์„ ํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์˜ ๋•…(land)์€ ์ด Nํ–‰ 4์—ด๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๊ณ , ๋ชจ๋“  ์นธ์—๋Š” ์ ์ˆ˜๊ฐ€ ์“ฐ์—ฌ ์žˆ์Šต๋‹ˆ๋‹ค. 1ํ–‰๋ถ€ํ„ฐ ๋•…์„ ๋ฐŸ์œผ๋ฉฐ ํ•œ ํ–‰์”ฉ ๋‚ด๋ ค์˜ฌ ๋•Œ, ๊ฐ ํ–‰์˜ 4์นธ ์ค‘ ํ•œ ์นธ๋งŒ ๋ฐŸ์œผ๋ฉด์„œ ๋‚ด๋ ค์™€์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋‹จ, ๋•…๋”ฐ๋จน๊ธฐ ๊ฒŒ์ž„์—๋Š” ํ•œ ํ–‰์”ฉ ๋‚ด๋ ค์˜ฌ ๋•Œ, ๊ฐ™์€ ์—ด์„ ์—ฐ์†ํ•ด์„œ ๋ฐŸ์„ ์ˆ˜ ์—†๋Š” ํŠน์ˆ˜ ๊ทœ์น™์ด ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค๋ฉด,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

๋กœ ๋•…์ด ์ฃผ์–ด์กŒ๋‹ค๋ฉด, 1ํ–‰์—์„œ ๋„ค๋ฒˆ์งธ ์นธ (5)๋ฅผ ๋ฐŸ์•˜์œผ๋ฉด, 2ํ–‰์˜ ๋„ค๋ฒˆ์งธ ์นธ (8)์€ ๋ฐŸ์„ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๋งˆ์ง€๋ง‰ ํ–‰๊นŒ์ง€ ๋ชจ๋‘ ๋‚ด๋ ค์™”์„ ๋•Œ, ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ ์ˆ˜์˜ ์ตœ๋Œ€๊ฐ’์„ returnํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด ์ฃผ์„ธ์š”. ์œ„ ์˜ˆ์˜ ๊ฒฝ์šฐ, 1ํ–‰์˜ ๋„ค๋ฒˆ์งธ ์นธ (5), 2ํ–‰์˜ ์„ธ๋ฒˆ์งธ ์นธ (7), 3ํ–‰์˜ ์ฒซ๋ฒˆ์งธ ์นธ (4) ๋•…์„ ๋ฐŸ์•„ 16์ ์ด ์ตœ๊ณ ์ ์ด ๋˜๋ฏ€๋กœ 16์„ return ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค.

์ œํ•œ์‚ฌํ•ญ
ํ–‰์˜ ๊ฐœ์ˆ˜ N : 100,000 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜
์—ด์˜ ๊ฐœ์ˆ˜๋Š” 4๊ฐœ์ด๊ณ , ๋•…(land)์€ 2์ฐจ์› ๋ฐฐ์—ด๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
์ ์ˆ˜ : 100 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜
์ž…์ถœ๋ ฅ ์˜ˆ
land answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16

์ฝ”๋“œ ์‹œ์ž‘

function solution(land) {
    const result = []
    const len = land.length
    // ํ•œ ์นธ ์•ž์—์„œ ์‹œ์ž‘ํ•จ
    for(let i = 1; i < len ; i ++) {
        // ํ˜„ ๋•…์˜ ๊ฐ’์„ ๋ชจ๋‘ ์ˆœํšŒ
        land[i] = land[i].map((el,idx) => {
            // ์ด์ „ ๋•…์—์„œ ๋‚ด๊ฐ€ ๋ฐŸ์€ ์ค„์˜ ๊ฐ’์€ ์ œ๊ฑฐ
            const box = land[i-1].slice()
            box.splice(idx,1)
            // ๋‚ด๊ฐ€ ๋ฐŸ์€ ๋•…์˜ ๊ฐ’๊ณผ ์ด์ „ ๋•…์˜ ์ตœ๋Œ€๊ฐ’์„ ๋”ํ•ด์„œ return
            return el+ Math.max(...box)   
        })
    }
    // ๋งˆ์ง€๋ง‰ ์ค„์—์„œ ๊ฐ€์žฅ ํฐ ๊ฐ’ return
    return Math.max(...land[len-1])
}

profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€