문제

Programmers Lv3, 기둥과 보 설치

핵심

• 문제의 요구사항에 따라 기둥과 보를 설치하거나 제거하여, 남아있는 건축물을 정렬하여 반환하는 문제이다. 먼저 기둥과 보를 설치하는 방법을 알아보자.

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

• 기둥과 보를 설치하거나 제거할 때마다 위의 조건에 어긋나는지 검사한다. 만약 조건을 충족시키지 못했다면 해당 작업을 수행하지 않고 넘어간다.

• {1,0}에 설치한 기둥은 바닥에 설치하므로 조건을 충족한다.
• {1,1}에 설치한 보는 한쪽 끝부분이 기둥에 있으니 조건을 충족한다.
• {2,1}에 설치한 기둥은 보의 한쪽 끝부분에 있으므로 조건을 충족한다.
• {2,2}에 설치한 보는 한쪽 끝부분이 기둥에 있으니 조건을 충족한다.
• {5,0}에 설치한 기둥은 바닥에 설치하므로 조건을 충족한다.
• {6,1}에 설치한 기둥은 다른 기둥 위에 있으므로 조건을 충족한다.
• {4,2}에 설치한 보는 한쪽 끝부분이 기둥에 있으니 조건을 충족한다.
• {3,2}에 설치한 보는 양쪽 끝부분이 다른 보와 연결되어 있으니 조건을 충족한다.

접근 순서

1. 문제 요구사항에 따라 건축물을 추가하거나 삭제한다.
2. 기둥을 추가했을 때는 바닥에 설치했거나, 한쪽 끝부분이 보에 닿아 있거나, 아래 기둥이 설치되어야 한다.
   

boolean canPlaceGidung(int x, int y, List<int[]> ret) {
	return y == 0 || contains(ret, new int[]{x, y - 1, 0}) 
		|| contains(ret, new int[]{x - 1, y, 1}) 
		|| contains(ret, new int[]{x, y, 1});
}

3. 보를 추가했을 때는 한쪽 끝부분이 기둥에 있거나 양쪽 끝부분이 다른 보가 있어야 한다.
   

boolean canPlaceBo(int x, int y, List<int[]> ret) {
	return contains(ret, new int[]{x, y - 1, 0}) 
		|| contains(ret, new int[]{x + 1, y - 1, 0}) 
		|| (contains(ret, new int[]{x - 1, y, 1}) 
			&& contains(ret, new int[]{x + 1, y, 1}));
}

4. 기둥 또는 보를 삭제했을 때는 현재 건축물을 삭제하고, 전체 건축물을 하나씩 순회하면서 유효한지 검사한다. 만약 유효하지 않다면 현재 건축물을 다시 삽입한다. 이는 유효하지 않을 때 명령어를 건너뛰는 행위와 동일하게 동작한다.

ret.removeIf(e -> Arrays.equals(e, new int[]{x, y, type}));

public boolean isValid(List<int[]> ret) {
	for (int[] e : ret) {
		int x = e[0];
		int y = e[1];
		int type = e[2];

		if (type == 0) {
        	if (!canPlaceGidung(x, y, ret)) return false;
            continue;
        } 
		if (type == 1) {
			if (!canPlaceBo(x, y, ret)) return false;
		}
   }
   return true;
}

개선

시간복잡도

• $O(n^2)$
  

코드

import java.util.*;

class Solution {

    public int[][] solution(int n, int[][] build_frame) {
        
        List<int[]> ret = new ArrayList<>();

        for (int[] frame : build_frame) {
            int x = frame[0];
            int y = frame[1];
            int type = frame[2];
            int cmd = frame[3];

            if (cmd == 1) {
                if (type == 0) {
                    if (canPlaceGidung(x, y, ret)) { 
                        ret.add(new int[]{x, y, type});
                        continue; 
                    }
                } 
				if (type == 1) { 
                    if (canPlaceBo(x, y, ret)) ret.add(new int[]{x, y, type});
                }
            } else if (cmd == 0) {
                ret.removeIf(e -> Arrays.equals(e, new int[]{x, y, type}));
                if (!isValid(ret)) ret.add(new int[]{x, y, type});
            }
        }

        ret.sort((a, b) -> {
            if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
            if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
            return Integer.compare(a[2], b[2]);
        });

        return ret.toArray(new int[ret.size()][]);
    }

    boolean canPlaceGidung(int x, int y, List<int[]> ret) {
        return y == 0 || contains(ret, new int[]{x, y - 1, 0}) 
            || contains(ret, new int[]{x - 1, y, 1}) 
            || contains(ret, new int[]{x, y, 1});
    }

    boolean canPlaceBo(int x, int y, List<int[]> ret) {
        return contains(ret, new int[]{x, y - 1, 0}) 
            || contains(ret, new int[]{x + 1, y - 1, 0}) 
            || (contains(ret, new int[]{x - 1, y, 1}) 
                && contains(ret, new int[]{x + 1, y, 1}));
    }

    boolean contains(List<int[]> ret, int[] e) {
        for (int[] item : ret) {
            if (Arrays.equals(item, e)) return true;
        }
        return false;
    }
    
    boolean isValid(List<int[]> ret) {
        for (int[] e : ret) {
            int x = e[0];
            int y = e[1];
            int type = e[2];

            if (type == 0) {
                if (!canPlaceGidung(x, y, ret)) return false;
                continue;
            } 
		    if (type == 1) {
                if (!canPlaceBo(x, y, ret)) return false;
            }
        }
        return true;
    }
}