프로그래머스 ) 블록게임

programmers.co.kr/learn/courses/30/lessons/42894

코딩테스트 연습 - 블록 게임

---

 

구슬을 매번한개씩 내리는 것보다 한턴에 2XN줄을 내려 버려서 직사각형을 만들수 있는지 없는지 확인한다.

 

나올수 있는 직사각형은 2X3 , 3X2밖에 없으므로 모든 Y,X에 대해서 이중포문으로 확인하자

 

시간복잡도는 6*50^3으로 안전하다.

 

 

---

class Solution {
    public int solution(int[][] board) {
        int answer = 0;
		 int size = board.length;
	        boolean isChange = true;
	        while(isChange) { isChange = false;
	        // 2줄을 내림
	        for(int i=0;i<size;i++) {
	        	int y=0;while(y<size && board[y][i]==0)y++;
	        	if(1<y&&y<size) {y--;board[y][i]=-1;board[y-1][i]=-1;} 
	        	else if(y==1){y--;board[y][i]=-1;} }
	         for(int i=0;i<size;i++)for(int j=0;j<size;j++) {
	        	// ㅡ ㅣ 이모양의 -1개 같은숫자4개가이루어지면 변경가능 ischange = true로 해주고 그 값없애고 다끝나면 -1제거작업
	        	int mcnt=0;  int bcnt =0; int fnum = 0; boolean impossible= false;
	        	top :
	        	for(int y=i;y<i+3&&y<size;y++) {
	        		for(int x=j;x<j+2&&x<size;x++) {
	        			if(board[y][x]==-1)mcnt++;
	        			else if(board[y][x]!=0&&fnum==0) {fnum=board[y][x];bcnt++;}
	        			else if(board[y][x]!=0&&fnum==board[y][x]) bcnt++;
	        			else {
	        				impossible=true;break top;
	        			}
	        		}
	        	}
	        	if(!impossible&&mcnt==2&&bcnt==4) {
	        		answer++; isChange = true;
	        		for(int y=i;y<i+3;y++) {for(int x=j;x<j+2;x++) {board[y][x]=0;}}}
	        	if(isChange) continue;
	        	mcnt=0;   bcnt =0;  fnum = 0; impossible= false;
	        	stop :
	        	for(int y=i;y<i+2&&y<size;y++) {
	        		for(int x=j;x<j+3&&x<size;x++) {
	        			if(board[y][x]==-1)mcnt++;
	        			else if(board[y][x]!=0&&fnum==0) {fnum=board[y][x];bcnt++;}
	        			else if(board[y][x]!=0&&fnum==board[y][x]) bcnt++;
	        			else {
	        				impossible=true;break stop;
	        			}
	        		}
	        	}
	        	if(!impossible&&mcnt==2&&bcnt==4) {
	        		isChange = true; answer++;
	        		for(int y=i;y<i+2;y++) {for(int x=j;x<j+3;x++) {board[y][x]=0;}}}
	          }
	        	if(isChange) for(int i=0;i<size;i++)for(int j=0;j<size;j++)if(board[i][j]==-1)board[i][j]=0;
	        }
	        return answer;
    }
}