[프로그래머스]2020카카오블라인드:기둥과 보 설치 (java)

문제보러가기

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

이 문제는 주어진 룰에 맞게 구현을 할 수 있는가를 보는 문제였다. 단순 구현이라기에는 설치할 때와 삭제할 때 가능한지를 체크해야 하므로 좀 까다로웠다. 나의 경우에는 삭제 부분에 대해 어떻게 하지 고민하다가 다른 분들의 방법을 참고하였다.

 

 

 

 

문제풀이

-설치된 기둥과 보를 저장할 배열을 만든다. 같은 위치에 놓일 수 있으므로 배열을 기둥 따로 보 따로 만든다.

-설치된 여부만 판단하면 되므로 boolean배열로 만들었다.

-배열의 크기는 아래와 같은 이유로 [n+3][n+3]으로 해주었다. 

    ->기둥 설치 시 -1까지 확인 해야하므로 1부터 시작.

    ->보 설치시 +1까지 확인해야 함.

-주어진 build_frame 배열을 돌며 기둥일 경우, 보일 경우 각각의 경우에서 설치의 경우, 삭제의 경우를 판단하여 check함수에 인자를 전달해주면 된다.

-설치의 경우: 문제에 제시된 대로 설치가 가능한지 check함수로 판단하여 총 answer배열의 cnt를 ++해준다.

-삭제의 경우: 임의로 삭제한 후 나머지 설치되어있는 기둥과 보가 설치가 가능한지 판단하는 것으로 판단한다.

삭제가 가능한지 판단하는 것 == 삭제하면 나머지들이 설치되어 있을 수 있는지

삭제가 가능하다면 총 answer배열의 cnt를 --해준다.

-기둥과 보 배열을 돌며 true로 되어있는 것을 answer배열에 추가해준다. 인덱스 작은 순서 -> 기둥부터 탐색하므로 따로 배열 정렬을 해주지 않아도 된다.

 

-check함수는 코드로 보는 것이 더 직관적일 거 같으니 코드를 살펴보자!

 

 

 

class Solution {
    static boolean[][] column;
	static boolean[][] beam;
    public int[][] solution(int n, int[][] build_frame) {
     	column = new boolean[n+3][n+3];
		beam = new boolean[n+3][n+3];
		int cnt=0;
		for (int i = 0; i < build_frame.length; i++) {
        	//-1 연산이 있으므로 index 에러가 안나기 위해 1부터 시작
			int y = build_frame[i][0]+1;
			int x = build_frame[i][1]+1;
			
			// column
			if (build_frame[i][2] == 0) {
				//삭제
				if(build_frame[i][3]==0) {
					//삭제가 가능할 경우
					if(check('c',x,y,0)) {
						column[x][y]=false;
						cnt--;
					}
				}
				//설치
				else {
					if(check('c',x,y,1)) {
						column[x][y]=true;
						cnt++;
					}
					
				}
			}
			//beam
			else {
				//삭제
				if(build_frame[i][3]==0) {
					//삭제가 가능할 경우
					if(check('b',x,y,0)) {
						beam[x][y]=false;
						cnt--;
					}
				}
				//설치
				else {
					if(check('b',x,y,1)) {
						beam[x][y]=true;
						cnt++;
					}
				}
				
			}
//			}
		}
		int[][] answer = new int[cnt][3];
		int index=0;
		for(int j=1;j<beam.length;j++) {
			for(int i=1;i<beam.length;i++) {
				if(column[i][j]) {
					answer[index][0]=j-1;
					answer[index][1]=i-1;
					answer[index][2]= 0;
					index++;
				}
				if(beam[i][j]) {
					answer[index][0]=j-1;
					answer[index][1]=i-1;
					answer[index][2]= 1;
					index++;
				}

			}
		}
	    return answer;	
	}
	static boolean check(char kind,int x, int y ,int work) {
		boolean flag=true;
		//설치
		if(work==1) {
			//기둥
			if(kind == 'c') {
				return x==1 || beam[x][y-1] || beam[x][y] || column[x-1][y];
			}
			//보
			else {
				return column[x-1][y] || column[x-1][y+1] || (beam[x][y-1] && beam[x][y+1]);
			}
		}
		//삭제
		else {
			if(kind == 'c') column[x][y]=false;
			else beam[x][y]=false;
			
			for(int i=1;i<beam.length-1;i++) {
				for(int j=1;j<beam.length-1;j++) {
                //삭제 후 나머지 기둥과 보들이 조건에 부합하는지 check함수를 통해 확인
                //설치할 수 있는지로 판단하는 것
					if(column[i][j] && !check('c',i,j,1)) {
						flag=false;
					}
					if(beam[i][j] && !check('b',i,j,1)) {
						flag = false;
					}
				}
			}
            //임시로 삭제해놨던 기둥 혹은 보를 원래대로 돌려놓음
			if(kind=='c') column[x][y]=true;
			else beam[x][y] = true;
		}
		
		return flag;
	}

}