๋ฌธ์ ์ค๋ช
[๋ณธ ๋ฌธ์ ๋ ์ ํ์ฑ๊ณผ ํจ์จ์ฑ ํ ์คํธ ๊ฐ๊ฐ ์ ์๊ฐ ์๋ ๋ฌธ์ ์ ๋๋ค.]
N x M ํฌ๊ธฐ์ ํ๋ ฌ ๋ชจ์์ ๊ฒ์ ๋งต์ด ์์ต๋๋ค. ์ด ๋งต์๋ ๋ด๊ตฌ๋๋ฅผ ๊ฐ์ง ๊ฑด๋ฌผ์ด ๊ฐ ์นธ๋ง๋ค ํ๋์ฉ ์์ต๋๋ค. ์ ์ ์ด ๊ฑด๋ฌผ๋ค์ ๊ณต๊ฒฉํ์ฌ ํ๊ดดํ๋ ค๊ณ ํฉ๋๋ค. ๊ฑด๋ฌผ์ ์ ์ ๊ณต๊ฒฉ์ ๋ฐ์ผ๋ฉด ๋ด๊ตฌ๋๊ฐ ๊ฐ์ํ๊ณ ๋ด๊ตฌ๋๊ฐ 0์ดํ๊ฐ ๋๋ฉด ํ๊ดด๋ฉ๋๋ค. ๋ฐ๋๋ก, ์๊ตฐ์ ํ๋ณต ์คํฌ์ ์ฌ์ฉํ์ฌ ๊ฑด๋ฌผ๋ค์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ ค๊ณ ํฉ๋๋ค.
์ ์ ๊ณต๊ฒฉ๊ณผ ์๊ตฐ์ ํ๋ณต ์คํฌ์ ํญ์ ์ง์ฌ๊ฐํ ๋ชจ์์
๋๋ค.
์๋ฅผ ๋ค์ด, ์๋ ์ฌ์ง์ ํฌ๊ธฐ๊ฐ 4 x 5์ธ ๋งต์ ๋ด๊ตฌ๋๊ฐ 5์ธ ๊ฑด๋ฌผ๋ค์ด ์๋ ์ํ์
๋๋ค.
์ฒซ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (0,0)๋ถํฐ (3,4)๊น์ง ๊ณต๊ฒฉํ์ฌ 4๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (2,0)๋ถํฐ (2,3)๊น์ง ๊ณต๊ฒฉํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ด 4๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋๋ ์ํ๊ฐ ๋ฉ๋๋ค.
์ธ ๋ฒ์งธ๋ก ์๊ตฐ์ด ๋งต์ (1,0)๋ถํฐ (3,1)๊น์ง ํ๋ณตํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ฉด ์๋์ ๊ฐ์ด 2๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์๋ค๊ฐ ๋ณต๊ตฌ๋๊ณ 2๊ฐ์ ๊ฑด๋ฌผ๋ง ํ๊ดด๋์ด์๋ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ง์ง๋ง์ผ๋ก ์ ์ด ๋งต์ (0,1)๋ถํฐ (3,3)๊น์ง ๊ณต๊ฒฉํ์ฌ 1๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ด 8๊ฐ์ ๊ฑด๋ฌผ์ด ๋ ํ๊ดด๋์ด ์ด 10๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋ ์ํ๊ฐ ๋ฉ๋๋ค. (๋ด๊ตฌ๋๊ฐ 0 ์ดํ๊ฐ ๋ ์ด๋ฏธ ํ๊ดด๋ ๊ฑด๋ฌผ๋, ๊ณต๊ฒฉ์ ๋ฐ์ผ๋ฉด ๊ณ์ํด์ ๋ด๊ตฌ๋๊ฐ ํ๋ฝํ๋ ๊ฒ์ ์ ์ํด์ฃผ์ธ์.)
์ต์ข ์ ์ผ๋ก ์ด 10๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์ง ์์์ต๋๋ค.
๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ํ๋ด๋ 2์ฐจ์ ์ ์ ๋ฐฐ์ด board
์ ์ ์ ๊ณต๊ฒฉ ํน์ ์๊ตฐ์ ํ๋ณต ์คํฌ์ ๋ํ๋ด๋ 2์ฐจ์ ์ ์ ๋ฐฐ์ด skill
์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง๋๋ค. ์ ์ ๊ณต๊ฒฉ ํน์ ์๊ตฐ์ ํ๋ณต ์คํฌ์ด ๋ชจ๋ ๋๋ ๋ค ํ๊ดด๋์ง ์์ ๊ฑด๋ฌผ์ ๊ฐ์๋ฅผ returnํ๋ solutionํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
์ ํ์ฌํญ
์ ํ์ฑ ํ ์คํธ ์ผ์ด์ค ์ ํ ์ฌํญ
ํจ์จ์ฑ ํ ์คํธ ์ผ์ด์ค ์ ํ ์ฌํญ
์ ์ถ๋ ฅ ์
board | skill | result |
---|---|---|
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] | [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] | 10 |
[[1,2,3],[4,5,6],[7,8,9]] | [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] | 6 |
์ ์ถ๋ ฅ ์ ์ค๋ช
๋ฌธ์ ์์์ ๊ฐ์ต๋๋ค.
<์ด๊ธฐ ๋งต ์ํ>
์ฒซ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (1,1)๋ถํฐ (2,2)๊น์ง ๊ณต๊ฒฉํ์ฌ 4๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ ๋ฒ์งธ๋ก ์ ์ด ๋งต์ (0,0)๋ถํฐ (1,1)๊น์ง ๊ณต๊ฒฉํ์ฌ 2๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋ฎ์ถ๋ฉด ์๋์ ๊ฐ์ ์ํ๊ฐ ๋ฉ๋๋ค.
๋ง์ง๋ง์ผ๋ก ์๊ตฐ์ด ๋งต์ (2,0)๋ถํฐ (2,0)๊น์ง ํ๋ณตํ์ฌ 100๋งํผ ๊ฑด๋ฌผ์ ๋ด๊ตฌ๋๋ฅผ ๋์ด๋ฉด ์๋์ ๊ฐ์ ์ํฉ์ด ๋ฉ๋๋ค.
์ด, 6๊ฐ์ ๊ฑด๋ฌผ์ด ํ๊ดด๋์ง ์์์ต๋๋ค. ๋ฐ๋ผ์ 6์ return ํด์ผ ํฉ๋๋ค.
์ ํ์๊ฐ ์๋ด
๋์ ํ์ด
ํด๋น ๋ฌธ์ ๋ Brute Force์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํ๋ฉด ๋ฐ๋์ ์๊ฐ ์ด๊ณผ ์ค๋ฅ๊ฐ ๋์จ๋ค.
์นด์นด์ค ํด์ค ํ์ด์ง ๋ฅผ ์ฐธ๊ณ ํ์ฌ imos ์๊ณ ๋ฆฌ์ฆ์ ํ์ฉํ์ฌ ๋์ ํฉ ๋ฌธ์ ๋ฅผ ํจ์จ์ ์ผ๋ก ํ ์ ์์ด์ผ ํ๋๋ฐ, ๊ฐ๋จํ๊ฒ ์ค๋ช ํ์๋ฉด
// ํด๋น ๋ฐฐ์ด์ 1๋ฒ์งธ ๋ถํฐ 2๋ฒ์งธ ์ธ๋ฑ์ค์ +5๋ฅผ ํด์ฃผ๊ณ ์ถ์ ๋
const want = [1,2,3,4]
// ๋ณํ๋ฅผ ์ฃผ์ด์ผ ํ ์๋ [2,3] ์ผ๋ก ๊ธธ์ด๊ฐ 2 ์ง๋ง ํ๋๋ฅผ ๋ ์ถ๊ฐํ์ฌ ๋ณํ๋ฅผ ์ค ์๋ฅผ 1๋ฒ์งธ ์ธ๋ฑ์ค์ ๋์ด๊ฒ ํ๊ณ ์ค๊ฐ์ ์์นํ ์๋ 0์ ๋ฐฐ์นํ ๋ค์ ๋ง์ง๋ง ์ธ๋ฑ์ค์ -1์ ๊ณฑํด์ค ์๋ฅผ ์์น์ํจ๋ค.
const imos = [0,5,0,-5]
// ํด๋น ๋ฐฐ์ด์ ๋๋ฒ์งธ ์ธ๋ฑ์ค ๋ถํฐ ๋ง์ง๋ง ๊น์ง ๋ชจ๋ 1๋ฒ์งธ ์ธ๋ฑ์ค์ ๊ฐ์ ๋ํด์ค๋ค.
[5,5,0]
// ์ํ๋ ์ธ๋ฑ์ค์ ๋ง๊ฒ ๋น ๊ณต๊ฐ์ 0์ผ๋ก ์ฑ์์ ๊ธฐ์กด ๋ฐฐ์ด๊ณผ ๋ํด์ค
imos = [0,5,5,0]
want.map((el,idx) => el+imos[idx])
return want // [1,7,8,4]
function solution(board, skill) {
const base = Array.from({length:board.length+1},(_,i) => Array(board[0].length+1).fill(0))
skill.forEach(s => {
// ๋ฐ๋ฏธ์ง ๋๋ ํ๋ณต
const dmg = !(s[0]-1) ? -1 : 1
// ์์ ์ขํ
const [startY,startX] = s.slice(1,3)
// ์ข
๋ฃ ์ขํ
const [endY,endX] = s.slice(3,5)
// ๊ฐ
const val = s[5]
// ํ์ฌ์์น
base[startY][startX] += val * dmg
// x์ถ ๋์์น+1
base[startY][endX+1] += -val * dmg
// y์ถ ๋์์น+1
base[endY+1][startX] += -val * dmg
// x์ถ ๋์์น+1, y์ถ ๋์์น+1
base[endY+1][endX+1] += val * dmg
})
// ์์ชฝ์์ ์๋์ชฝ์ผ๋ก +=
for(let row = 0 ; row < base.length - 1 ; row ++) {
for(let col = 0 ; col < base[row].length ; col++) {
base[row+1][col] += base[row][col]
}
}
// ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก +=
for(let row = 0 ; row < base.length ; row ++) {
for(let col = 0 ; col < base[row].length -1 ; col++) {
base[row][col+1] += base[row][col]
}
}
// ๊ธฐ์กด ๋ฐฐ์ด๊ณผ ํฉ์นจ
for(let row = 0 ; row < board.length ; row ++) {
for(let col = 0 ; col < board[row].length ; col++) {
board[row][col]+=base[row][col]
}
}
return board.flat(Infinity).filter(item => item > 0).length
}