[프로그래머스] 기둥과 보 설치

문제 설명

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

문제 풀이

• 구현이 조금 까다로운 문제였다.
• 구현을 간단히 하기 위해 크게 2가지 인사이트가 사용되었다.

  1. 설치와 삭제 가능 여부를 하나의 함수로 통일하였다.
     - 설치 시에 사용하는 설치 가능 여부 메서드를 삭제에 활용하기 위해서 삭제를 수행할 때 현재 위치의 기둥/보를 우선 삭제하고 영향을 주는 기둥/보에 대해 설치 가능 여부를 판단 후 하나라도 설치가 불가하면 삭제 불가능, 모두 설치 가능하면 삭제 가능 하도록 구현하였다.
  2. 결과 배열을 위해 정렬이 아닌 간단한 방법 사용
     - 결과 배열은 (x, y, a) 기준 ASC 정렬을 사용하는데 이는, 기둥/보 배열에서 x-> y -> a 순으로 순회하며 map[x][y][a] == 1일 경우 배열에 추가하는 방식으로 결과 배열을 구성했다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N;
    public int[][][] map = new int[101][101][2];

    //설치 가능한지 여부 확인
    public boolean isInstallable(int x, int y, int a) {
        boolean flag = false;
        //기둥 설치
        if (a == 0) {
            //1. 바닥에 설치하는 경우
            if (y == 0) flag = true;
            //2. 보의 한쪽 끝에 설치하는 경우
            if (x-1 >= 0 && map[x-1][y][1] == 1) flag = true;
            if (x+1 <= N && map[x][y][1] == 1) flag = true;
            //3. 다른 기둥 위에 설치하는 경우
            if (y-1 >= 0 && map[x][y-1][0] == 1) flag = true;
        }
        //보 설치
        else {
            //1. 한쪽 끝이 다른 기둥 위
            if (y-1 >= 0 && map[x][y-1][0] == 1) flag = true;
            if (y-1 >= 0 && map[x+1][y-1][0] == 1) flag = true;
            //2. 양쪽 끝이 다른 보
            if (x-1 >= 0 && x+2 <= N && map[x-1][y][1] == 1 && map[x+1][y][1] == 1) flag = true;
        }
        return flag;
    }

    public int[][] solution(int n, int[][] build_frame) {
        //초기화
        N = n;
        int resultCnt = 0;
        //명령어 수행 시작
        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 == 1) {
                if (isInstallable(x, y, a)) {
                    map[x][y][a] = 1;
                    resultCnt++;
                }
            }
            //삭제하는 경우
            else {
                boolean flag = true;
                //현재 구조물 삭제
                map[x][y][a] = 0;

                //가능 여부 확인
                //기둥 삭제
                if (a == 0) {
                    if (x-1 >= 0 && map[x-1][y+1][1] == 1 && !isInstallable(x-1, y+1, 1)) flag = false;
                    if (x+1 <= N && map[x][y+1][1] == 1 && !isInstallable(x, y+1, 1)) flag = false;
                    if (y+2 <= N && map[x][y+1][0] == 1 && !isInstallable(x, y+1, 0)) flag = false;
                }
                //보 삭제
                else {
                    if (y+1 <= N && map[x][y][0] == 1 && !isInstallable(x, y, 0)) flag = false;
                    if (y+1 <= N && map[x+1][y][0] == 1 && !isInstallable(x+1, y, 0)) flag = false;
                    if (x-1 >= 0 && map[x-1][y][1] == 1 && !isInstallable(x-1, y, 1)) flag = false;
                    if (x+2 <= N && map[x+1][y][1] == 1 && !isInstallable(x+1, y, 1)) flag = false;
                }

                //가능 여부에 따라 삭제 혹은 복원
                //삭제
                if (flag)
                    resultCnt--;
                //복원
                else
                    map[x][y][a] = 1;
            }
        }

        int[][] result = new int[resultCnt][3];
        int ind = 0;
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= N; j++) {
                for (int a = 0; a <= 1; a++) {
                    if (map[i][j][a] == 1) {
                        result[ind][0] = i;
                        result[ind][1] = j;
                        result[ind++][2] = a;
                    }
                }
            }
        }
        return result;
    }
}