문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/60061

구현방법

조건

1. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나 또다른 기둥 위여야함.
2. 보는 한쪽 끝 부분이 기둥 위에 있거나 ,또는 양쪽 끝 부분이 다른 보와 동시에 연결되어열림.

x,y , a ,b 형태

a : 구조물

0 -> 기둥

1 -> 보

b : 설치 삭제 선택

0 -> 삭제

1 -> 설치

맨위의 조건에 맞지 않는다면 무시됨.

결과물

-> x,y ,a -> a는 구조물 종류

x좌표 기준 정렬 x좌표가 같으면 y자표 기준 오름차순 정렬

조건 체크

-> 설치가능 하면 진행 아니면 아웃

보는 오른쪽으로 설치 됨

기둥은 위쪽으로 설치됨.

설치가 됬을때 -> 설치 좌표와 구조물 종류를 적어둔다. -> List형식으로 적어두고 나중에 배열로 바꾸던가 하면되지 않을까

2가지 함수

기둥일때 조건체크

보 일때 조건 체크

조건을 통과시에 (좌표, 구조물)을 저장 -> 여러번 돌 예정

기둥이 설치 가능한 공간

• 바닥 위 -> (x,0) 인지

• 보의 한쪽 끝 ->본인의 왼쪽 좌표에 보가 있는지

• 또 다른 기둥 -> 본인의 아래 좌표에 기둥 이 있는지

보가 가능한 공간

• 한쪽 끝부분이 기둥 위 -> 본인의 아래 좌표가 기둥인지 또는 본인의 오른쪽 아래 좌표가 기둥인지
• 양쪽 끝부분이 다른 보와 연결 본인의 왼쪽 좌표가 보 이면서 오른쪽 좌표도 보 인경우

-> 완탐이 가능하기 때문에

일단 삭제하는 건축물을 삭제 시켜놓고

지금까지 건축된 건축물들이 건축이 되는지 체크한다

• 건축이 안된다면 다시 list에 넣어준다

처음에 생각하지 못한것

: 같은 좌표에 기둥과 보가 둘다 있는 경우가 있다. -> map으로 표현할꺼면 기둥이 설치 배열과 보 설치 배열 2가지로 나눠서 푸는게 편하다.

: 리스트로 담아둘 경우는 사실 contains문으로 필요한 좌표에 있는지 체크하면된다.

remove의 경우 그냥 remove(object)를 할 경우 hash값이 다르기 때문에 remove가 제대로 되지 않는다.

만약 객체를 지우고 싶은 경우에는 해당 객체 클래스안에 hashcode를 오버라이딩해서 해쉬코드를 만들고 비교하는 함수가 있어야한다.

참고 블로그 : https://loosie.tistory.com/448

이 문제는 구현을 잘하는가 못하는 가로 문제를 풀 수 있는가 없는가가 판단이 된다. 설치부분은 어느정도 이해가 빠르게 됬지만 삭제 구현에서 막혀서 다른 분의 블로그를 참고해서 풀었다.

알고리즘

구현!

CODE

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {

    //건설한 건축물들 모아놓기.
    List<Build> buildList = new ArrayList<>();

    int size = 0;

    public int[][] solution(int n, int[][] build_frame) {
        int[][] answer = {};
        size = n;

        //kind 종류
        //check : 0 삭제 1 설치
        for (int idx = 0; idx < build_frame.length; idx++) {
            int col = build_frame[idx][0];
            int row = build_frame[idx][1];
            int kind = build_frame[idx][2];
            int check = build_frame[idx][3];

            Build builder = new Build(col, row, kind);

            //설치
            if (check == 1) {
                //기둥
                if (kind == 0) {
                    if (isPossiblePillar(builder)) {
                        buildList.add(builder);
                    }

                    //보 설치
                } else {
                    if (isPossibleBeam(builder)) {
                        buildList.add(builder);
                    }

                }

                //삭제
            } else {
                buildList.remove(builder);
                if(!isDelete()){
                    buildList.add(builder);
                }
            }
        }


        //정렬
        Collections.sort(buildList, (o1, o2) -> {
            if (o1.col == o2.col) {
                if(o1.row == o2.row){
                    return o1.type - o2.type;
                }
                return o1.row - o2.row;
            }

            return o1.col - o2.col;
        });


        answer = new int[buildList.size()][3];
        for (int idx = 0; idx < buildList.size(); idx++) {
            Build build = buildList.get(idx);
            answer[idx][0] = build.col;
            answer[idx][1] = build.row;
            answer[idx][2] = build.type;
        }

        return answer;
    }

    private boolean isDelete() {

        for(Build list : buildList){
            if(list.type == 0){
                if(!isPossiblePillar(list)){
                    return false;
                }

            }else{
                if(!isPossibleBeam(list)){
                    return false;
                }
            }
        }
        return true;
    }


    //기둥 설치가 가능한지 체크
    public boolean isPossiblePillar(Build build) {
        int row = build.row;
        int col = build.col;

        //바닥 위인지
        if (build.row == 0) {
            return true;
        }

        //보의 한쪽 끝인지 (세로 좌표는 같으면서 가로 좌표가 -1 인경우)
        if (col -1 >= 0 && buildList.contains(new Build(col-1,row,1))) {
            return true;
        }
        //현재 위치 보 도 확인
        if(buildList.contains(new Build(col,row,1))){
            return true;
        }

        //또 다른 기둥 위인지
        if (row -1 >= 0  && buildList.contains(new Build(col,row-1,0))) {
            return true;
        }


        return false;

    }

    //보 설치가 가능한지 체크
    public boolean isPossibleBeam(Build build) {
        int row = build.row;
        int col = build.col;
        //한쪽 끝부분이 기둥위인가
        if (row -1 >= 0 && (buildList.contains(new Build(col,row-1,0)) || buildList.contains(new Build(col+1,row-1,0)))) {
            return true;
        }
        //현재 좌표의 왼쪽에 보가 있고 오른쪽에도 보가 있는가
        if (col-1 >= 0 && (buildList.contains(new Build(col-1,row,1)) && buildList.contains(new Build(col+1,row,1)))) {
            return true;
        }

        return false;
    }

    public class Build {
        //row -> 세로좌표
        int col;

        //가로 좌표
        int row;
        // 0 은 기둥, 1은 보
        int type;

        public Build(int col, int row, int type) {
            this.col = col;
            this.row = row;
            this.type = type;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Build other = (Build) obj;
            if (type != other.type)
                return false;
            if (col != other.col)
                return false;
            if (row != other.row)
                return false;
            return true;
        }
        @Override
        public int hashCode() {
            final int prime = 31;
            int result = 1;
            result = prime * result + type;
            result = prime * result + col;
            result = prime * result + row;
            return result;
        }

    }
}