[프로그래머스/자바] 기둥과 보 설치 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 3 문제다.

 

특별한 알고리즘 적용 없이 조건을 잘 검사하여 기둥이랑 보를 설치/삭제하면 되는 구현 문제다.

삭제하는 작업이 들어올 경우 삭제하면 안되는 여러 경우가 있기 때문에

(기둥 아래에 보가 있는지, 기둥 위 오른쪽 보가 양쪽 보와 연결되어 있는지 등등..)

이를 어떻게 다 검사할지 어려웠다.

 

먼저 삭제하는 작업이 들어올 경우 바로 삭제한 후,

삭제했을 때 조건을 만족하지 않는 보나 기둥이 있는 경우 삭제한 보/기둥을 원래대로 되돌리면 된다.

조건을 만족하지 않는 보/기둥을 검사하는 방법은 

설치할 때 검사하는 조건과 동일하므로 canPillar, canBeam이라는 함수를 만들어 사용했다.

 

즉, 설치할 보/기둥이 조건을 만족하는지, 삭제했을 때 보/기둥이 조건을 만족하는지 확인하기 위해서는

문제에 나와있는 규칙 두개만을 검사하면 된다.

 

처음엔 삭제하기 전 여러 경우의 수를 하나하나 체크할 조건들을 다 구현하려고 했어서 어려웠는데,

설치할 때와 삭제했을 때의 조건이 동일하다는 것만 안다면 쉽게 풀 수 있는 것 같다.

 

 

그리고 조건을 검사할 때 배열의 인덱스를 벗어날 수 있으므로

보/기둥을 설치할 배열을 상하좌우 1씩 늘렸다. 

원래는 0~N까지 보/기둥이 설치되지만, 배열을 늘렸으므로 1~N+1까지 설치된다.

 

1	1	1
1	1	1
1	1	1

	1	1	1
	1	1	1
	1	1	1

즉, 늘리기 전 위의 표와 같지만, 늘린 후는 아래의 표처럼 배열이 구성된다.

이 때 1로 채워진 부분만 보/기둥이 설치될 수 있다.

 

 

 

 

 

배운점 및 느낀점

html/css에서만 padding을 배웠던 거 같은데 

이렇게 배열을 늘리는 것도 padding이라고 하는지 처음 알았다.

조건 검사가 까다로울 경우 하나하나 배열의 범위를 넘어가는지 확인하는 것보다,

배열을 늘리는 게 더 간단할 수 있다는 걸 배웠다!

 

 

import java.util.*;

class Solution {
    static boolean[][] pillar;
	static boolean[][] beam;
	static int N;
    
    public int[][] solution(int n, int[][] build_frame) {
		N = n;
		pillar = new boolean[n + 2][n + 2];
		beam = new boolean[n + 2][n + 2];

		for(int i=0;i<build_frame.length;i++) {
			int x = build_frame[i][0] + 1;
			int y = build_frame[i][1] + 1;
			int a = build_frame[i][2]; // 0: 기둥, 1: 보
			int b = build_frame[i][3]; // 0: 삭제, 1: 설치

			if(a == 0 && b == 1) {
				if(canPillar(x, y)) 
					pillar[x][y] = true;
			}
			else if(a == 0 && b == 0) {
				pillar[x][y] = false;

				if(!canDelete())
					pillar[x][y] = true;
			}
			else if(a == 1 && b == 1) {
				if(canBeam(x, y))
					beam[x][y] = true;
			}
			else { // a == 1 && b == 0
				beam[x][y] = false;

				if(!canDelete())
					beam[x][y] = true;
			}
		}

		ArrayList<int[]> list = new ArrayList<>();

		for(int i=1;i<=N+1;i++)
			for(int j=1;j<=N+1;j++) {
				if(pillar[i][j])
					list.add(new int[] {i - 1, j - 1, 0});
				if(beam[i][j])
					list.add(new int[] {i - 1, j - 1, 1});
			}
		
		list.sort((o1, o2) -> {
			if(o1[0] == o2[0] && o1[1] == o2[1])
				return o1[2] - o2[2];
			else if(o1[0] == o2[0])
				return o1[1] - o2[1];
			else
				return o1[0] - o2[0];
		});

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

		for(int i=0;i<ans.length;i++)
			ans[i] = list.get(i);

		return ans;
	}

	static boolean canDelete() {
		for(int i=1;i<=N+1;i++)
			for(int j=1;j<=N+1;j++)
				if(pillar[i][j] && !canPillar(i, j))
					return false;
				else if(beam[i][j] && !canBeam(i, j))
					return false;
		return true;
	}

	static boolean canPillar(int x, int y) {
		// 바닥이거나 기둥, 보 위인 경우 기둥 설치 가능
		if(y == 1 || pillar[x][y - 1] || beam[x][y] || beam[x - 1][y])
			return true;
		return false;
	}

	static boolean canBeam(int x, int y) {
		// 양 끝이 보로 연결되어 있거나 한쪽 끝이 기둥인 경우 보 설치 가능
		if((beam[x - 1][y] && beam[x + 1][y]) || pillar[x][y - 1] || pillar[x + 1][y - 1])
			return true;
		return false;
	}
}