기둥과 보 설치 - '2020 카카오 코딩 테스트'

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

n x n 매트릭스 벽면의 '기둥'과 '보'를 설치 하는 명령어 리스트를 주어, 설치 결과를 반환하는 문제 입니다. 

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.

• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

위 조건의 맞춰서 설치하고 구현만 잘해주면 되는 문제 입니다.  하지만, 코드 실행에서는 통과 하지만, 제출 할 경우 통과 하지 못했습니다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Page329 {
    // 기둥과 보 설치
    // https://programmers.co.kr/learn/courses/30/lessons/60061

    public static void main(String[] args) {
        int n = 5;
        ///int[][] build_frame = new int[][]{{1,0,0,1},{1,1,1,1},{2,1,0,1},{2,2,1,1},{5,0,0,1},{5,1,0,1},{4,2,1,1},{3,2,1,1}};
        int[][] build_frame = new int[][]{{0,0,0,1},
                                        {2,0,0,1},
                                        {4,0,0,1},
                                        {0,1,1,1},
                                        {1,1,1,1},
                                        {2,1,1,1},
                                        {3,1,1,1},
                                        {2,0,0,0},
                                        {1,1,1,0},
                                        {2,2,0,1}};
        new Page329().solution(n, build_frame);
    }

    List<int[]> result;
    int n;

    public int[][] solution(int n, int[][] build_frame) {
        // 임시 결과 List
        this.result = new ArrayList<int[]>();
        this.n = n;

        // build_frame 을 반복문을 돌면서 구현
        for (int i = 0; i < build_frame.length; i++) {
            int x = build_frame[i][0];
            int y = build_frame[i][1];
            int pillar = build_frame[i][2];
            int install = build_frame[i][3];

            if (install == INSTALL) install(x, y, pillar);
            else unInstall(x, y, pillar);
        }

        // result x, y, 기둥 -> 보 순으로 정렬
        result.sort(sortPillarAndBeam());

        int[][] answer = new int[result.size()][3];
        answer = result.toArray(answer);
        return answer;
    }

    private Comparator<int[]> sortPillarAndBeam() {
        return (o1, o2) -> {
            if (o1[0] == o2[0]) {
                if (o1[1] == o2[1]) {
                    return o1[2] == PILLAR ? 1 : -1;
                } else {
                    return o1[1] - o2[1];
                }
            } else {
                return o1[0] - o2[0];
            }
        };
    }

    private void install(int x, int y, int pillar) {
        if (isInstallPillar(x, y, pillar) ||
                isInstallBeam(x, y, pillar)) {
            int[] a = new int[3];
            a[0] = x;
            a[1] = y;
            a[2] = pillar;
            result.add(a);
        }
    }

    private void unInstall(int x, int y, int pillar) {
        // 삭제하기
        for (int i = 0; i < result.size(); i++) {
            // 삭제
            if (result.get(i)[0] == x && result.get(i)[1] == y && result.get(i)[2] == pillar) {
                result.remove(i);

                // 삭제 후 남아 있는 기둥과 보는 아래 조건을 만족해야 한다.
                for (int j = 0; j < result.size(); j++) {
                    int x1 = result.get(j)[0];
                    int y1 = result.get(j)[1];
                    int pillar1 = result.get(j)[2];

                    // 아래 조건을 한번 이라도 만족 한다면
                    // 삭제 했던 배열 다시 추가
                    if (!isInstallPillar(x1, y1, pillar1) && !isInstallBeam(x1, y1, pillar1)) {
                        // 삭제 했던 배열 다시 추가
                        result.add(new int[]{x, y, pillar});
                        break;
                    }
                }
                break;
            }
        }
    }

    private final int INSTALL = 1;
    private final int PILLAR = 0;
    private final int BEAM = 1;
    private final int FLOOR = 0;

    private boolean isInstallPillar(int x, int y, int pillar) {
        // 기둥이 아니라면 false
        if (pillar != PILLAR)
            return false;

        // 기둥은 바닥 위에 있거나
        // 보의 한쪽 끝 부분 위에 있거나,
        // 또는 다른 기둥 위에 있어야 합니다.
        if (!isOutOfMapForPillar(x, y) &&
                (isOnTheFloor(y) ||
                isAboveOneEndOfTheBeam(x, y) ||
                isOnThePillar(x, y)))
            return true;

        return false;
    }

    private boolean isInstallBeam(int x, int y, int pillar){
        // 보가 아니면 false
        if (pillar != BEAM)
            return false;

        // 보는 한쪽 끝 부분이 기둥 위에 있거나,
        // 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
        if (!isOutOfMapForBeam(x, y) &&
                (isAboveThePillar(x, y) ||
                isConnectedWithOtherBeam(x, y)))
            return true;

        return false;
    }

    private boolean isOutOfMapForPillar(int x, int y) {
        return n < x || (n - 1) < y || 0 > x || 0 > y;
    }

    private boolean isOnTheFloor(int y){
        return (y == FLOOR);
    }

    private boolean isAboveOneEndOfTheBeam(int x, int y) {
        for (int i = 0; i < result.size(); i++) {
            if (result.get(i)[0] == x && result.get(i)[1] == y && result.get(i)[2] == BEAM)
                return true;
            if (result.get(i)[0] == (x - 1) && result.get(i)[1] == y && result.get(i)[2] == BEAM)
                return true;
        }
        return false;
    }

    private boolean isOnThePillar(int x, int y) {
        for (int i = 0; i < result.size(); i++)
            if (result.get(i)[0] == x && result.get(i)[1] == (y - 1) && result.get(i)[2] == PILLAR)
                return true;
        return false;
    }

    private boolean isOutOfMapForBeam(int x, int y) {
        return (n - 1) < x || n < y || 0 > x || 0 > y;
    }

    private boolean isAboveThePillar(int x, int y) {
        for (int i = 0; i < result.size(); i++) {
            if (result.get(i)[0] == x && result.get(i)[1] == (y - 1) && result.get(i)[2] == PILLAR)
                return true;
            if (result.get(i)[0] == (x + 1) && result.get(i)[1] == (y - 1) && result.get(i)[2] == PILLAR)
                return true;
        }
        return false;
    }

    private boolean isConnectedWithOtherBeam(int x, int y) {
        boolean left = false;
        boolean right = false;

        for (int i = 0; i < result.size(); i++) {
            if (result.get(i)[0] == (x - 1) && result.get(i)[1] == y && result.get(i)[2] == BEAM)
                left = true;
            if (result.get(i)[0] == (x + 1) && result.get(i)[1] == y && result.get(i)[2] == BEAM)
                right = true;
            if (left && right)
                return true;
        }

        return false;
    }
}

 

 

아무리 찾아봐도, 왜 틀렸는지 잘 모르겠습니다. 따라서, 다른 분의 소스를 찾아 봤습니다. 아래 소스가 다른 분 소스 입니다.

import java.util.*;


public class Page329_2 {

    // 기둥과 보 설치
    // https://programmers.co.kr/learn/courses/30/lessons/60061
    static final int PILLAR = 0;
    static final int BEAM = 1;
    static final int DESTRUCT = 0;
    static final int CONSTRUCT = 1;

    boolean[][] pillars, beams; // 기둥, 보

    public int[][] solution(int n, int[][] build_frame) {
        int structureCount = 0;

        // 기둥과 보를 따로 관리 한다.
        // 구현의 편의성
        pillars = new boolean[n + 3][n + 3];
        beams = new boolean[n + 3][n + 3];

        for (int[] frame : build_frame) {
            int x = frame[0] + 1;
            int y = frame[1] + 1;
            // 기둥인지 보인지
            int structureType = frame[2];
            // 설치 할지, 삭제 할지
            int commandType = frame[3];

            // 설치 한다면,
            if (commandType == CONSTRUCT) {
                if (structureType == PILLAR && canConstructPillar(x, y)) {
                    pillars[x][y] = true;
                    structureCount++;
                }
                if (structureType == BEAM && canConstructBeam(x, y)) {
                    beams[x][y] = true;
                    structureCount++;
                }
            } else if (commandType == DESTRUCT) {
                // 삭제
                if (structureType == PILLAR) {
                    pillars[x][y] = false;
                } else if (structureType == BEAM) {
                    beams[x][y] = false;
                }

                if (canDestruct(n)) {
                    structureCount--;
                    continue;
                }

                // 삭제 할수 없으므로, 되살린다.
                if (structureType == PILLAR) {
                    pillars[x][y] = true;
                } else if (structureType == BEAM) {
                    beams[x][y] = true;
                }
            }
        }

        int index = 0;
        int[][] answer = new int[structureCount][3];

        for (int i = 1; i <= n + 1; ++i) {
            for (int j = 1; j <= n + 1; ++j) {
                if (pillars[i][j]) answer[index++] = new int[]{i - 1, j - 1, PILLAR};
                if (beams[i][j]) answer[index++] = new int[]{i - 1, j - 1, BEAM};
            }
        }
        return answer;
    }

    private boolean canConstructPillar(int x, int y) {
        return y == 1 || pillars[x][y - 1] || beams[x][y] || beams[x - 1][y];
    }

    private boolean canConstructBeam(int x, int y) {
        return pillars[x][y - 1] || pillars[x + 1][y - 1] || (beams[x - 1][y] && beams[x + 1][y]);
    }

    private boolean canDestruct(int n) {
        for (int i = 1; i <= n + 1; ++i) {
            for (int j = 1; j <= n + 1; ++j) {
                if (pillars[i][j] && !canConstructPillar(i, j)) {
                    return false;
                }
                if (beams[i][j] && !canConstructBeam(i, j)) {
                    return false;
                }
            }
        }

        return true;
    }
}

저의 소스랑 비교해 봤지만, 여전히 제 소스가 어디서 틀렸는지 모르겠습니다. 다른 분 소스의 경우는 pillars[][](기둥), beams[][](보) 기둥과 보를 따로 2차원 배열의 할당하여, true, false를 담아 사용 했습니다. 이를 통해 구현 또한 편해 졌지만, 제 소스와 비교했을때, isAboveOneEndOfTheBeam(int x, int y) 함수에는 반복문이 들어간것의 비해,  canConstructPillar(int x, int y) 함수에는 반복문이 들어가지 않습니다. boolean[][] pillars, boolean[][] beams가 데이터를 기억해 두었다가, 반복문을 사용하지 않고 바로, 연산 할수 있었습니다. 자료구조를 잘 만드는것이 정말 중요 한것을 다시, 한번 느낄 수 있었습니다.