[프로그래머스] 무인도 여행: 코드 예제로 쉽게 이해하기 (Javascript)

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

1. 문제 정의

섬마다 놓인 식량이 있다. 각 섬에 있는 식량의 총량을 오름차순의 배열에 나타내고, 없다면 -1을 담아 리턴하라.

 

2. 제한 사항

1) 격자의 크기는 3이상, 100이하이다.

2) 각 값은 X 또는 1~9 사이의 자연수이다.

 

3. 풀이

1) 공간 복잡도 = O(N^2)

• 2-D Array: 하나의 섬 여부를 나타낼 입력 크기와 같은 2차원 배열 1개.

2) 시간 복잡도 = O(N^2)

 

3) 알고리즘

• 같은 섬을 찾는다.
• 섬 별 식량의 총합을 구한다.
• 섬별 식량 총량을 오름차순으로 정렬한다.

 

여기에서, 1. 같은 섬을 찾는다의 경우, 추상화를 많이 해둬, 좀 더 상세히 설명하자면 Recursion으로 풀이했다.

 

1. 조회하고 있는 element(숫자)를 토대로, 상하좌우를 탐색한다.

2. 배열의 끝이거나, 이미 섬이 정해지거나, 바다('X')일 경우 0을 리턴한다.

3. 들른적 없으면서, 섬이 이어진 경우, 같은 알고리즘을 현재 위치 기준으로 반복한다.

 

4. 예제 코드

function solution(maps) {
    var answer = [];
    var maxGroupId = 0;
    
    const findIslands = (x, y, groupId) => {
        if(x < 0 || x >= islands.length) return;
        if(y < 0 || y >= islands[x].length) return;
        if(islands[x][y] > 0) return ;
        if(maps[x][y] === 'X') return ;
        
        islands[x][y] = groupId;
        findIslands(x + 1, y, groupId);
        findIslands(x - 1, y, groupId);
        findIslands(x, y + 1, groupId);
        findIslands(x, y - 1, groupId);
    }
    
    var islands = Array.from({length: maps.length}, () => Array(maps[0].length).fill(0));
    
    for(let i = 0; i < maps.length; i++) {
        for(let j = 0; j < maps[i].length; j++) {
            if(maps[i][j] === 'X') {
                continue;
            } else if (islands[i][j] > 0) {
                continue;
            } else {
                findIslands(i, j, ++maxGroupId);
            }
        }
    }
    
    const totalGroceries = Array(maxGroupId).fill(0);
    for(let i = 0; i < maps.length; i++) {
        for(let j = 0; j < maps[i].length; j++) {
            if(islands[i][j] > 0){
                totalGroceries[islands[i][j] - 1] += Number(maps[i][j]);
            }
        }
    }
    
    totalGroceries.sort((a, b) => a - b);
    
    if(maxGroupId === 0) answer.push(-1);
    else answer = [...totalGroceries];
    
    return answer;
}

 

더 효율적인 방법이 있다면 알려주세요. 감사합니다.