[프로그래머스] 가장 큰 정사각형 찾기 -Java

 

https://programmers.co.kr/learn/courses/30/lessons/12905

코딩테스트 연습 - 가장 큰 정사각형 찾기

class Solution {
		int size;
		public int solution(int[][] board) {
			size=0;
			int answer = 1;
			int H=board.length;
			int W=board[0].length;
			int oneCnt=0;
			
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					if(board[i][j]==1) {
						
						if(i+size>H || j+size>W) 
							continue;
						isRect(i,j,board,W,H);
						oneCnt++;
						if((size*size)>=(H-1)*(H-1) || (size*size)>=(W-1)*(W-1))
							return size*size;
					}
				}
			}

			if(oneCnt!=0 && size==0) size=1;
			return size*size;
		}

		private void isRect(int x, int y, int[][] board, int W, int H) {
			int cnt=1;
			int nx=x;
			int ny=y;
			
			while(true) {
				
				if(nx+cnt<H && ny+cnt<W) {
					//행확인
					for(int j=ny; j<=ny+cnt; j++) {
						if(board[nx+cnt][j]!=1) return;
					}
					//열확인
					for(int i=nx; i<=nx+cnt; i++) {
						if(board[i][ny+cnt]!=1) return;
					}
					
					size=Math.max(size, ++cnt);					
				}
				else return ;
				
			}
			
		}
	}

1차 풀이 

소요시간 : 20분 

 

풀긴..했는데 효율성이 0점이다....ㅎ 효율성이 좋은 알고리즘을 짜볼려고 노력했지만 생각이 나지 않았고.. 노가다(?)로 풀었다.

 

일단 로직은 이러하다.. 1을 만나면 위의 그림처럼 크기가 몇 인 정사각형인지 판별한다!  나름 가지치기를 현재 구한 size보다 큰 정사각형이 나올 수 없는 좌표라면 skip을 했다.

 

 

 

 

class Solution {
		public int solution(int[][] board) {
			int answer = 0;
			int W=board[0].length;
			int H=board.length;
			int oneCnt=0;
			
			for(int i=0; i<H; i++) {
				for(int j=0; j<W; j++) {
					if(i<1 || j<1) {
						if(board[i][j]==1) oneCnt++;
						continue;
					}
					
					if(board[i][j]==1) board[i][j]=Math.min(board[i-1][j-1], Math.min(board[i-1][j], board[i][j-1]))+1;
					answer=Math.max(answer, board[i][j]);
				}
			}
			if(oneCnt>=1 && answer==0) answer=1;
			return answer*answer;
		}
	}

 

 

 

 

2차 풀이 

효율성을 만족시키기 위해 사람들의 도움을 조금 빌렸다..^^ 

 

문제를 찾아보니... DP로 푸는 문제였다!! DP일 줄을 생각도 못했는데

아무튼 큰 로직은

4번의 값이 0이 아니라면 1,2,3번의 값을 비교해 최소값을 찾은 뒤에 4번 자리에 그 최솟값에 1을 더한 값을 넣어준다.

 

최솟값을 찾는 이유는 하나의 0이 있다면 정사각형이 성립될 수 없으므로 1 이상의 값들만 이어나가기 위해서이다.  또한 1을 더해주는 이유는 정사각형이라면 길이를 늘려주기위함이고 정사각형이 아니라면 남은 1의 값이 다른 곳에서 정사각형을 이룰 수 있기 때문이다.

 

 

참조

codedrive.tistory.com/53