2020 KAKAO BLIND - 기둥과 보 설치 / Java

1. 문제

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

 

처음 풀었을 때 2시간 걸렸는데 반 정도는 맞고 반 정도는 틀렸다.. 도저히 예외 테스트 케이스를 잡을 방법이 생각이 안 나서 싹 다 지우고 다시 풀었다. 근데 테스트 케이스만 맞고 다 틀리더라.. 

배열의 칸이 아닌 줄을 사용해서 푸는 문제라 배열안에 객체를 선언해서 객체 요소로 풀려고 했었는데 도저히 안 나와서 접근방법을 바꿨더니 훨씬 짧고 효율적으로 풀렸다.

 

2. 접근

구현상 어려운 알고리즘은 없는데.. 접근 방법과 조건에 맞게 구현하는 것이 상당히 까다롭다.

 

기둥과 보를 설치하는 조건을 찾는 거는 어렵지 않다.

문제는 삭제하는 조건을 생각하다보니 경우의 수가 너무 많아서 다른 방법을 생각해봤다. 

 

삭제가 가능한지 보는게 아니라 삭제를 하고 나서 남아있는 구조물이 조건을 만족하는지 검사하는 방법을 사용했다. 기둥과 보를 설치하기 위한 조건과 동일하기 때문에 코드 재사용도 되고 build_frame 배열 자체의 크기가 크지 않기에 가능했다.

 

아무튼.. 그렇게 조건에 맞게 생성, 삭제 한 뒤 2차원 배열에 담아서 정렬해서 마무리!

 

3. 코드

import java.util.*;
class Solution {
    public int[][] solution(int n, int[][] build_frame) {
        ArrayList<Frame> list = new ArrayList<>();

        for(int i=0;i<build_frame.length;i++){
            int x = build_frame[i][0];
            int y = build_frame[i][1];
            int a = build_frame[i][2];
            int b = build_frame[i][3];

            if(b==0){ // 삭제
                list.remove(new Frame(x,y,a));
                if(!isDelete(list,x,y)){ // 삭제가 불가능 하다면
                    list.add(new Frame(x,y,a));
                }
            } else { // 생성
                if(a==0){ // 기둥 생성
                    if(isMakeColumn(list,x,y)){
                        list.add(new Frame(x,y,a));
                    }
                } else { // 보 생성
                    if(isMakeBeam(list,x,y)){
                        list.add(new Frame(x,y,a));
                    }
                }
            }
        }

        int[][] result = new int[list.size()][3];

        for(int i=0;i< result.length;i++){
            Frame frame = list.get(i);
            result[i][0] = frame.x;
            result[i][1] = frame.y;
            result[i][2] = frame.type;
        }

        Arrays.sort(result, (o1, o2) -> {
            if(o1[0]==o2[0]){
                if(o1[1]==o2[1]){
                    return o1[2]-o2[2];
                } else {
                    return o1[1]-o2[1];
                }
            } else {
                return o1[0]-o2[0];
            }
        });

        return result;
    }

    public boolean isMakeColumn(ArrayList<Frame> list, int x, int y){
        if(y==0 || list.contains(new Frame(x,y-1,0)) || list.contains(new Frame(x-1,y,1)) 
        || list.contains(new Frame(x,y,1))){
            return true;
        } else {
            return false;
        }
    }

    public boolean isMakeBeam(ArrayList<Frame> list, int x, int y){
        if(list.contains(new Frame(x,y-1,0)) || list.contains(new Frame(x+1,y-1,0)) 
        || (list.contains(new Frame(x-1,y,1)) && list.contains(new Frame(x+1,y,1)))){
            return true;
        } else {
            return false;
        }
    }

    public boolean isDelete(ArrayList<Frame> list, int x, int y){
        for(int i=0;i<list.size();i++){
            Frame frame = list.get(i);
            if(frame.type==0){ // 기둥이면
                if(!isMakeColumn(list, frame.x, frame.y)){  // 지금 자리에 기둥을 세울 수 있다면
                    return false; // 삭제 불가
                }
            } else { // 보이면
                if(!isMakeBeam(list, frame.x, frame.y)){
                    return false;
                }
            }
        }
        return true; // 이상없으면 삭제 가능
    }
}

class Frame{
    int x;
    int y;
    int type;

    Frame(int x, int y, int type){
        this.x = x;
        this.y = y;
        this.type = type;
    }

    @Override
    public boolean equals(Object object){
        if(object == null){
            return false;
        }
        if(getClass() != object.getClass()){
            return false;
        }
        Frame frame = (Frame)object;

        if(x==frame.x && y==frame.y && type==frame.type){
            return true;
        } else {
            return false;
        }
    }
}

 

4. 결과

 

 

ps.. 카카오 기출문제 풀 때 마다 느끼는 거지만 문제 하나 죽치고 잡고 있어도 못 풀거나 2시간 이상 걸리는 문제가 많은데 1차 컷이 7개 중 4개라니.. 생각할수록 너무 어렵다