프로그래머스 프렌즈4블록 (level 2)

나의 1차 풀이 (풀이 시간 : 31분)

function solution(m, n, board) {
    var answer = 0;
    let arr = board.map(x=>x.split(""));
    // console.log(arr);
    while (true) {
        let remove = [];
        for (let x = 0; x < m-1; x++) {
            for (let y = 0; y < n-1; y++) {
                if (arr[x][y] !== 0 && arr[x][y] === arr[x+1][y] && arr[x][y] === arr[x][y+1] && arr[x][y] === arr[x+1][y+1]) {
                    remove.push([x,y]);
                }
            }
        }
        if (remove.length === 0) {
            // console.log("end");
            break;
        } 
        
        for (let x of remove) {
            arr[x[0]][x[1]] = 0;
            arr[x[0]+1][x[1]] = 0;
            arr[x[0]][x[1]+1] = 0;
            arr[x[0]+1][x[1]+1] = 0;
        }
        for (let x = m-2; x >= 0; x--) {
            for (let y = 0; y <= n-1; y++) {
                if (arr[x][y] !== 0 && arr[x+1][y] === 0) {
                    [arr[x][y], arr[x+1][y]] = [arr[x+1][y], arr[x][y]];
                }
            }
        }
    }
    // console.log(arr);
    for (let x = 0; x <= m-1; x++) {
        for (let y = 0; y <= n-1; y++) {
            if (arr[x][y] === 0) {
                answer++;
            }
        }
    }
    return answer;
}

2차원 배열을 만들고, 탐색하면서 2X2 블록이 같은 원소를 가진다면 좌측 상단의 좌표를 저장한다. 탐색이 끝나면, 좌표들을 찾아가서 2X2 블록을 0으로 만든다. 그리고 0과 0이 아닌 값을 스왑하는 식으로 값을 내린다. 이 과정을 제거할 원소가 없을 떄까지 반복한다.

** 문제점
0으로 변환한 원소 위에 0이 아닌 원소들이 2개 이상 있다면, 0 바로 윗 원소를 제외한 나머지 원소들은 하강하지 않는다. 알고리즘 상, 원소가 값이 있고, 그 아래 원소가 0이면 스왑을 하기 때문이다.

나의 2차 풀이

function solution(m, n, board) {
    var answer = 0;
    let arr = board.map(x=>x.split(""));
    // console.log(arr);
    while (true) {
        let remove = [];
        for (let x = 0; x < m-1; x++) {
            for (let y = 0; y < n-1; y++) {
                if (arr[x][y] !== 0 && arr[x][y] === arr[x+1][y] && arr[x][y] === arr[x][y+1] && arr[x][y] === arr[x+1][y+1]) {
                    remove.push([x,y]);
                }
            }
        }
        if (remove.length === 0) {
            // console.log("end");
            break;
        } 
        
        for (let x of remove) {
            arr[x[0]][x[1]] = 0;
            arr[x[0]+1][x[1]] = 0;
            arr[x[0]][x[1]+1] = 0;
            arr[x[0]+1][x[1]+1] = 0;
        }

        for (let i = 0; i <= m-1; i++){
            for (let x = 0; x < m-1; x++) {
                for (let y = 0; y <= n-1; y++) {
                    if (arr[x][y] !== 0 && arr[x+1][y] === 0) {
                        [arr[x][y], arr[x+1][y]] = [arr[x+1][y], arr[x][y]];
                    }
                }
            }
        }

    }
    // console.log(arr);

    for (let x = 0; x <= m-1; x++) {
        for (let y = 0; y <= n-1; y++) {
            if (arr[x][y] === 0) {
                answer++;
            }
        }
    }
    return answer;
}

스왑하는 과정에 for문을 하나 더 씌워서 하강하지 않는 원소가 없게 만들었다. 그런데 이렇게 하면 시간복잡도가 O(n^4)여서 실행시간이 오래걸린다.

다른 사람의 풀이

다른 사람들의 풀이도 O(n^4)의 시간복잡도를 가졌다. 어떻게해서든 푸는 것이 중요하다는 것을 다시 한번 느낀다.