프로그래머스[JS] > 무인도 여행

🔥문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/154540

프로그래머스

 

🔥첫번째 시도 (런타임 에러) 

호기롭게 풀었지만 런타임 에러... 🤔

function solution(maps) {
    var answer = [];

    // visit 관련 map
    const visit_map = maps.map((str,x)=>{
        let temp = []
        for(let y=0; y<=str.length-1; ++y){
            temp.push(str[y]!=='X')
        }
        return temp
    })

    // {1: 10, 2:1, 3:2 } 와 같이 같은섬의 식량점수를 담을 obj
    let score_map = {}
    
    // 연결되어 있는 땅은 모두 같은 숫자로 표기
    const dfs =(position,mark)=>{
        const [x,y] = position
        visit_map[x][y] = false
        if(score_map[mark]){
            score_map[mark]+=Number(maps[x][y])
        }else{
            score_map[mark]=Number(maps[x][y])
        }
             
        // 상하좌우
        let move = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
        move.forEach(([new_x,new_y])=>{
            // 존재하고, true 이면
            if(visit_map[new_x]&&visit_map[new_x][new_y]===true){
                dfs([new_x,new_y],mark)
            }
        })
    }


    let mark = 0;
    for(let i=0; i<=maps.length-1; ++i){
        for(let j=0; j<=maps[0].length-1; ++j){
            if(visit_map[i][j]===true){
                ++mark
                dfs([i,j],mark)
            }
        }
    }

    answer = Object.values(score_map)    
    return answer.length ? answer.sort((a,b)=> a-b) : [-1] ;

}

 

 

🔥두번째 시도 ( 실패 - 특정 케이스 런타임 에러 )

결과는 마찬가지로 또 15, 16, 18, 19번 케이스 런타임 에러가 나타난다.

function solution(maps) {
    var answer = [];
    let score_map = {}
    maps = maps.map((line)=> line.split(''))
    
    // 연결되어 있는 땅은 모두 같은 숫자로 표기
    const dfs =(position,mark)=>{
        let [x,y] = position
        let score = maps[x][y]
            
        if(answer[mark]){
            answer[mark]+=Number(score)
        }else{
            answer[mark]=Number(score)
        }
        maps[x][y] ='X'
        // 상하좌우
        let move = [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]
        
        
        move.forEach((new_position)=>{
            let [nx,ny] = new_position
            if(nx>=0 && nx<=maps.length-1 && ny>=0 && ny<=maps[0].length-1){
                if(maps[nx][ny]!=='X'){
                    dfs([nx,ny],mark)
                }
            }
        })
    }


    let mark = 0;
    let [max_x,max_y]=[maps.length-1,maps[0].length-1]
    for(let i=0; i<=max_x; ++i){
        for(let j=0; j<=max_y; ++j){
            if(maps[i][j]!=='X'){
                dfs([i,j],mark)
                ++mark
            }
        }
    }

    return answer.length ? answer.sort((a,b)=> a-b) : [-1] ;
}

 

 

🔥세번째 시도 ( 성공 )

이번엔 조금 따로 섬마다의 점수를 리스트업 하기 위한 score_map 객체를 만들지 않고 다이렉트로 answer에 섬마다의 합산 점수를 직접 push 해줬다. 흠 .... 아무래도 런타임 에러는 메모리 제한을 초과했기 때문에 나타났던거 같다.

function solution(maps) {
    var answer = [];
    maps = maps.map((line)=> line.split(''))

    const dfs =(position)=>{
        let [x,y] = position
        if(x>=0 && x<maps.length && y>=0 && y<maps[0].length && maps[x][y]!=='X'){
            let score = Number(maps[x][y])
            maps[x][y] = 'X'
            return score + dfs([x+1,y]) + dfs([x-1,y]) + dfs([x,y+1]) + dfs([x,y-1])
        }else{
            return 0
        }
    }



    let [max_x,max_y]=[maps.length-1,maps[0].length-1]
    for(let i=0; i<=max_x; ++i){
        for(let j=0; j<=max_y; ++j){
            if(maps[i][j]!=='X'){
                answer.push(dfs([i,j]))
            }
        }
    }

    return answer.length ? answer.sort((a,b)=> a-b) : [-1] ;
}

 

🔥후기

1,2 번째 특정 케이스 런타임 에러는 아마 메모리 사용량을 초과해서 인 것 같다. 그렇다면 1,2 번 풀이와 3번 풀이의 차이는 무엇일까? 그건 바로 재귀함수가 돌 때마다 점수를 담는 객체나 배열에 특정 key나 index로 접근하여 값을 계속해서 갱신하기 때문이다. 3번째 문제의 경우 재귀함수를 돌때마다 객체에 접근하는 것이 아닌 총합을 구한다음 최종적으로 점수를 담는 answer 배열에 담기 때문에 메모리 사용량이 더 적다고 이해하면 될 것이다.  

 

별도로 처음에 maps[1] = 'abcd' 인 경우 maps[1][0] = '9' 라고 선언해도 maps[1]은 그대로 'abcd' 임을 (문자열 특정 배열 수정 불가능) 간과하고 문제를 풀어서 쓸때없는 데 시간을 많이 허비했는데 다음에 문자열을 다룰 때 이 점도 주의 해야겠다.