[プログラマ]柱とビームのインストール

問題を解く

問題の説明は、関連リンクを参照してください.
solution関数を呼び出すときにnをパラメータとして与えるのは理由があります.n*nは座標平面のサイズ範囲を制限します.最終的に、座標の個数は限られており、地図を用いてすべての座標とその座標に位置する構造物を対応させることができる.
まず,ソリューションの内部クラスとして,座標平面に対応するCoordinateクラスを宣言する.HashMapのキーとして使用するため,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);
    }
}

次に、Structureクラスを宣言します.このクラスには、始点、終点座標を表すstart、endおよび柱であるかどうかを保存するtypeフィールドが含まれます.

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);
    }
}

次に、各座標を、その座標を始点または終点とする構造物配列に対応するマッピングstructuresonCoordinateとする.上、下、左、右をインデックスとすると、その座標に対して上、下、左、右の構造の参照値が得られる.

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

次に,各構築物を構築するbuild関数を実現する.また、構築可能かどうかを判断するisBuilable関数も実装されています.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メソッドと削除可能か否かを判断するisremobileメソッドも実施した.柱が見えるか見えるかによって除去可能な条件が異なるので,関数を単独で実現する.

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;
}

その後,ソリューションアプローチを実現した.すべての座標に対応する構造をmapで配列し、始点と終点に対応する構造配列に構造物を配置するか、除去します.そして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;
}