강의로 돌아가기
moonjh9392

JS 효율성 테스트 질문 (코드주의)

function solution(maps) {
    const N = maps.length-1
    const M = maps[0].length-1
    const direction = [[0, -1], [0, 1], [-1, 0], [1, 0]]

    let queue = [[0, 0, 1]]
    maps[0][0] = 0

    while (queue.length > 0) {
        const [x,y,count] = queue.shift()
        if (x == N && y == M) {
            return count
        }

        for (d of direction) {
            const next = [x + d[0],y + d[1],count+1]
            if ((maps[next[0]] && maps[next[0]][next[1]]) &&
                maps[next[0]][next[1]] === 1) {
            maps[next[0]][next[1]] = 0

            queue.push(next)
            }
        }
    }
    return -1
}

while에서 for 한번 돌려서 O(n2 ) 인데요 다른분들 코드 봐도 O(n2 ) 인데
이코드는 왜 효율성에서 4개 전부 시간초과가 나올까요??

  • moonjh9392

    어제는 효율성 4개 전부 실패 나왔는데

    moonjh9392―2022.12.15 20:52
  • moonjh9392

    오늘은 효율성 4개 전부 성공 나오네요.. 뭘까요?

    moonjh9392―2022.12.15 20:52
  • semanticist21

    문제그지같넹

    semanticist21―2023.05.11 21:55
2 개의 답변
leeuihyun

..저도그러네요?

semo

n, m이 1인 경우는 주어지지 않으므로 (next[0] === n && next[1] === m)라면 cnt + 1를 반환해서 queue반복 횟수를 줄여보시면 좋을 것 같아요

답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.