[프로그래머스] 기둥과 보 설치

문제 풀이

문제 설명은 해당 링크를 참조하자.

solution 함수 호출 시 매개변수로 n을 준 것에는 이유가 있다. n * n 크기로 좌표평면의 범위를 제한하기 위해서다. 결국 좌표의 개수는 유한하게 되는 것이고, map을 이용하여 모든 좌표와 해당 좌표에 위치한 구조물을 대응시킬 수 있게 되는 것이다.

우선 Solution의 내부 클래스로 좌표 평면에 해당하는 Coordinate 클래스를 선언한다. HashMap의 key로 사용해야 하기 때문에 equals와 hashCode 메서드를 오버라이딩한다.

class Coordinate{
    public int x, y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        Coordinate p = (Coordinate) o;
        return this.x == p.x && this.y == p.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

그 다음 시작점, 끝점의 좌표를 나타내는 start, end와 기둥인지 보인지 여부를 저장하는 type을 필드로 가지는 Structure 클래스를 선언한다.

class Structure{
    public Coordinate start, end;
    public int type;

    public Structure(int x, int y, int type){
        start = new Coordinate(x, y);
        this.type = type;
        end = type == 0 ?
              new Coordinate(x, y + 1) : new Coordinate(x + 1, y);
    }
}

그 다음 각 좌표들과 해당 좌표를 시작점 혹은 끝점으로 하는 구조물들의 배열을 대응시키는 map인 structuresOnCoordinate을 선언한다. 인덱스로 up, down, left, right를 넣으면 해당 좌표를 기준으로 위, 아래, 왼쪽, 오른쪽으로 가는 구조물의 참조값을 얻을 수 있다.

class Solution {
    int up = 0, right = 1, down = 2, left = 3;
    HashMap<Coordinate, Structure[]> structuresOnCoordinate;
    
    ...
}

그 다음 각 구조물을 건설하는 build 함수를 구현한다. 또한 build가 가능한지 여부를 판단해주는 isBuildable 함수를 구현한다. isBuildable 함수는 기둥이냐 보이냐에 따라 조건이 달라지기 때문에 isPillarBuildable, isFloorBuildable 함수도 구현한다.

public void build(){
    if(!isBuildable()) return;
    if(type == 0){
        structuresOnCoordinate.get(start)[up] = this;
        structuresOnCoordinate.get(end)[down] = this;
    }else{
        structuresOnCoordinate.get(start)[right] = this;
        structuresOnCoordinate.get(end)[left] = this;
    }
}

public boolean isBuildable(){
    return type == 0 ? isPillarBuildable() : isFloorBuildable();
}

public boolean isPillarBuildable(){
    if(start.y == 0) return true;

    for(int i = right;i < 4;i++){
        if(structuresOnCoordinate.get(start)[i] != null) return true;
        // 해당 좌표에서 아래, 왼, 오른쪽에 구조물 없으면 건설 불가능
    }

    return false;
}

public boolean isFloorBuildable(){
    if(structuresOnCoordinate.get(start)[down] != null 
    || structuresOnCoordinate.get(end)[down] != null)
        return true;
        // 한쪽 끝에 기둥이 있으면 가능

    if(structuresOnCoordinate.get(start)[left] != null 
    && structuresOnCoordinate.get(end)[right] != null)
        return true;
        // 양쪽 끝에 보가 있으면 가능

    return false;
}

마찬가지로 구조물을 제거하는 remove 메서드와, 제거할 수 있는지 여부를 판단하는 isRemovable 메서드를 구현한다. 기둥이냐 보이냐에 따라 제거 가능한 조건이 달라지므로 함수를 따로 구현한다.

public void remove(){
    if(!isRemovable()) return;
    if(type == 0){
        structuresOnCoordinate.get(start)[up] = null;
        structuresOnCoordinate.get(end)[down] = null;
    }else{
        structuresOnCoordinate.get(start)[right] = null;
        structuresOnCoordinate.get(end)[left] = null;
    }
}

public boolean isRemovable(){
    return type == 0 ? isPillarRemovable() : isFloorRemovable();
}

public boolean isPillarRemovable(){
    Structure[] point = structuresOnCoordinate.get(end); // 해당 Pillar와 자식들의 교점
    if(point[up] != null && point[left] == null && point[right] == null) return false;
    if(point[left] != null){
        Structure[] leftPoint = 
            structuresOnCoordinate.get(point[left].start);
        if(leftPoint[down] == null 
           && (leftPoint[left] == null || point[right] == null))
            return false;
    }
    if(point[right] != null){
        Structure[] rightPoint = structuresOnCoordinate.get(point[right].end);
        if(rightPoint[down] == null 
            && (point[left] == null || rightPoint[right] == null))
            return false;
    }

    return true;
}

public boolean isFloorRemovable(){
    Structure[] leftPoint = structuresOnCoordinate.get(start);
    Structure[] rightPoint = structuresOnCoordinate.get(end);

    if(leftPoint[up] != null
    // 왼쪽 위에 기둥이 있을 때 제거 불가능 조건
       && leftPoint[down] == null && leftPoint[left] == null)
        return false;

    if(rightPoint[up] != null
    // 오른쪽 위에 기둥이 있을 때 제거 불가능 조건
       && rightPoint[down] == null && rightPoint[right] == null)
        return false;

    if(leftPoint[left] != null){
    // 왼쪽에 보가 있을 때 제거 불가능 조건
        Structure[] leftLeftPoint = 
            structuresOnCoordinate.get(leftPoint[left].start);
        if(leftLeftPoint[down] == null && leftPoint[down] == null)
            return false;
    }

    if (rightPoint[right] != null) {
    // 오른쪽에 보가 잇을 때 제거 불가능 조건
        Structure[] rightRightPoint = 
            structuresOnCoordinate.get(rightPoint[right].end);
        if(rightPoint[down] == null && rightRightPoint[down] == null) 
            return false;
    }

    return true;
}

그 다음 solution 메서드를 구현하였다. map을 통하여 모든 좌표에 대하여 Structure의 배열을 대응시킨 뒤, 구조물들을 시작점과 끝점에 대응되는 Structure 배열에 넣어주거나 제거하는 방식이다. 그 다음 ArrayList에 정해진 순서대로 넣고, 다시 배열로 옮겨놓아서 답을 반환한다.

public int[][] solution(int n, int[][] build_frame) {
    structuresOnCoordinate = new HashMap<>();
    for(int i = 0;i <= n;i++){
        for(int j = 0;j <= n;j++){
            Structure[] temp = new Structure[4];
            Arrays.fill(temp, null);
            structuresOnCoordinate.put(new Coordinate(i, j), temp);
        }
    }

    for(int[] builder: build_frame){
        int startX = builder[0];
        int startY = builder[1];
        int type = builder[2];
        boolean buildOrDelete = builder[3] == 1;

        if(buildOrDelete){
            Structure newStructure = new Structure(startX, startY, type);
            newStructure.build();
        }else{
            Structure removed = structuresOnCoordinate.get(new Coordinate(startX, startY))[type == 0 ? up : right];
            removed.remove();
        }
    }

    ArrayList<Structure> allStructures = new ArrayList<>();

    for(int i = 0;i <= n;i++){
        for(int j = 0; j <= n; j++){
            Structure[] point = 
                structuresOnCoordinate.get(new Coordinate(i, j));
            if(point[up] != null) allStructures.add(point[up]);
            if(point[right] != null) allStructures.add(point[right]);
        }
    }

    int[][] answer = new int[allStructures.size()][3];
    for(int i = 0;i < answer.length;i++){
        answer[i][0] = allStructures.get(i).start.x;
        answer[i][1] = allStructures.get(i).start.y;
        answer[i][2] = allStructures.get(i).type;
    }

    return answer;
}