[2020 KAKAO BLIND RECRUITMENT][JAVASCRIPT] 기둥과 보 설치

문제 바로가기

 

코딩테스트 연습 - 기둥과 보 설치

 

 

처음에는 기둥과 보를 만들 수 있는 자리를 배열로 만들었는데 이렇게 하니 너무 복잡해져서 현재 기둥과 보가 있는 좌표를 배열로 만들었다.

 

<문제 풀이 Logic>

1. 기둥과 보 배열을 만든다.

2. '추가'일 경우에는 기둥/ 보를 추가할 수 있는 지 확인한다. -> isColumnPossible(), isBeamPossible()

가능하면 추가해준다.

3. '삭제'일 경우에는 먼저 기둥/ 보를 삭제한 후 현재 남은 기둥과 보가 모두 2의 조건을 만족하는지 확인한다.

하나라도 2의 조건을 만족하지 못한다면 삭제한 기둥/ 보를 다시 원래 상태로 돌려준다. 

4. 모든 작업을 끝낸 후 기둥/ 보 배열에서 값이 1인 x, y를 answer에 추가해주고 sort 해준다. (이 때 다차원 배열인 경우 sort()함수를 그냥 사용하면 제대로 sort가 되지 않는다. sort() 함수를 재정의해서 사용한다.)

 

 

-전체 코드-

var real_column;
var real_beam;

function isColumnPossible(y, x) {
    console.log("(" + x + "," + y + ")");

    if (y == 1 || real_column[y - 1][x] == 1 || real_beam[y][x] == 1 || real_beam[y][x - 1] == 1)
        return true;
    return false;
}

function isBeamPossible(y, x) {
    console.log("(" + x + "," + y + ")");

    if (real_column[y - 1][x] == 1 || real_column[y - 1][x + 1] == 1 || ((real_beam[y][x - 1] == 1) && (real_beam[y][x + 1] == 1)))
        return true;
    return false;
}

function initialize(n) {
    real_column = new Array(n + 3);
    real_beam = new Array(n + 3);

    for (var i = 0; i < n + 3; i++) {
        real_column[i] = new Array(n + 3);
        for (var j = 0; j < n + 3; j++)
            real_column[i][j] = 0;
    }

    for (var i = 0; i < n + 3; i++) {
        real_beam[i] = new Array(n + 3);
        for (var j = 0; j < n + 3; j++) {
            real_beam[i][j] = 0;
        }
    }
}
function solution(n, build_frame) {
    var answer = [];

    initialize(n);

    for (var build = 0; build < build_frame.length; build++) {
        var item = build_frame[build];
        //console.log(item);
        var x = item[0] + 1;
        var y = item[1] + 1;
        var material = item[2];
        var type = item[3];

        if (type == 1)//추가
        {
            if (material == 0)//기둥
            {
                if (isColumnPossible(y, x)) {
                    real_column[y][x] = 1;
                    console.log("(" + x + ", " + y + ") 번째에 기둥 세움");
                }
            }
            else {
                if (isBeamPossible(y, x)) {
                    real_beam[y][x] = 1;
                    console.log("(" + x + ", " + y + ") 번째에 보 세움");
                }
            }
        }
        else//삭제
        {
            if (material == 0)//기둥
            {
                if (real_column[y][x] == 1)//기둥 존재하면
                {
                    real_column[y][x] = 0;//일단 삭제 !

                    //기둥 쪽에서 문제 생기는 지 확인
                    loop:
                    for (var i = 1; i <= n + 1; i++) {
                        for (var j = 1; j <= n + 1; j++) {
                            if (real_column[i][j] == 1 && !isColumnPossible(i, j)) {
                                real_column[y][x] = 1;
                                console.log("(" + x + ", " + y + ") 번째에 기둥 삭제 안됨 - 기둥 문제");
                                break loop;
                            }
                            if (real_beam[i][j] == 1 && !isBeamPossible(i, j)) {
                                real_column[y][x] = 1;
                                console.log("(" + x + ", " + y + ") 번째에 기둥 삭제 안됨 - 보 문제");
                                break loop;
                            }
                        }
                    }
                }
            }
            else//보
            {
                if (real_beam[y][x] == 1)//보 존재하면
                {
                    real_beam[y][x] = 0;

                    loop:
                    for (var i = 1; i <= n + 1; i++) {
                        for (var j = 1; j <= n + 1; j++) {
                            if (real_column[i][j] == 1 && !isColumnPossible(i, j)) {
                                real_beam[y][x] = 1;

                                console.log("(" + x + ", " + y + ") 번째에 보 삭제 안됨 - 기둥문제");

                                break loop;
                            }
                            if (real_beam[i][j] == 1 && !isBeamPossible(i, j)) {
                                real_beam[y][x] = 1;

                                console.log("(" + x + ", " + y + ") 번째에 보 삭제 안됨 - 보 문제");

                                break loop;
                            }
                        }
                    }
                }
            }
        }
    }

    for (var i = 1; i <= n + 1; i++) {
        for (var j = 1; j <= n + 1; j++) {
            if (real_column[i][j] == 1)
                answer.push([j - 1, i - 1, 0]);
            if (real_beam[i][j] == 1)
                answer.push([j - 1, i - 1, 1]);
        }
    }

    console.log("결과")

    // answer.sort(function (a, b) { // 오름차순
    //     return a[0] < b[0] ? -1 : a[1] < b[1] ? 0 : a[2] < b[2] ? 1 : 2;
    // });
    //answer.sort();
    answer.sort((a, b) => {
        if (a[0] > b[0]) {
            return 1;
        } else if (a[0] < b[0]) {
            return -1;
        } else {
            if (a[1] > b[1]) {
                return 1;
            } else if (a[1] < b[1]) {
                return -1;
            } else {
                if (a[2] > b[2]) {
                    return 1;
                } else if (a[2] < b[2]) {
                    return -1;
                }
            }
        }
    })

    for (var i = 0; i < answer.length; i++) {
        console.log(answer[i][0] + " " + answer[i][1] + " " + answer[i][2]);
    }
    return answer;
}