문제 링크
실패한 문제 풀이
- 실패한 풀이
이중 for문을 통해서 접근하는 방식을 취하니깐 효율성 테스트를 통과하지 못했다.
checkSize 메소드에서 다시 한번 가로길이를 확인해야 하는 부분에서 큰 시간을 잡아먹는것 같다. 예를들어 1이 연속으로 9개 나왔을때 맨 앞에서 9인것을 알았다면 그 옆은 자연스럽게 8인것을 알아야 한다고 생각한다.
그래서 생각한 것은 bfs, dp 였는데 이전값을 기억한다는 점에서 dp로 접근해야 한다는 생각이 들었다.
- 실패한 코드
import java.util.*;
class Solution
{
public int solution(int [][]board){
int answer = 1;
int maxLen = Math.min(board.length,board[0].length);
for(int i=0; i<board.length; i++){
for(int j=0; j<board[i].length; j++){
if(board[i][j]==1){
answer = Math.max(answer,checkSize(answer,i,j,board));
}
}
}
return answer;
}
public int checkSize(int answer, int x,int y,int [][] board){
int cnt = 0; //가로 길이
for(int i=y; i<board[0].length; i++){
if(board[x][i]==0){
break;
}else{
cnt++;
}
}
//현재넓이보다 작으면 바로 컷...
if(answer>=cnt*cnt){
return -1;
}
//세로 체크
//가로의 길이가 전체 세로길이보다 크면 시마이...
if(cnt>board.length-x){
return -1;
}
int idx=x;
for(int i=0; i<cnt; i++){
if(board[idx++][y]==0){
return -1;
}else{
}
}
//가로 세로가 같다면 전체 체크
idx=x;
int idy=y+1;
for(int i=0; i<cnt-1; i++){
for(int j=0; j<cnt-1; j++){
if(board[idx+1][idy++]==0){
return -1;
}
}
idx++;
idy=y+1;
}
return cnt*cnt;
}
}문제 풀이
dp를 이용해서 문제를 해결했다.
board와 같은 크기의 dp 배열을 만들고
0번째 열과, 0번째 행에 있는 모든 값들을 board배열과 동일하게 만들었다.
for(int i=0; i<board.length; i++){
dp[i][0] = board[i][0];
sum+=dp[i][0];
}
for(int i=0; i<board[0].length; i++){
dp[0][i]=board[0][i];
sum+=dp[0][i];
}여기서 만약에 1개짜리 정사각형이 있을수도 있기에 초기값을 입력하는 과정에서
dp에 1의 값이 담길때마다 sum이라는 변수에 +1을 해줬다.
if(sum>0){
answer=1;
}dp[i][j]는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1]과 비교하여
자신이 넓이가 몇인 정사각형의 기준점이 되는지 나타내는 값이다.
예를들어
dp[i-1][j-1]=1 | dp[i-1][j]=1
dp[i][j-1]=1 | dp[i][j] =1
인경우 길이가 2인 정사각형이 되므로 dp[i][j]=4 이다.
ex)
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
이라는 board 배열이 있다.
초기 dp값은 아래처럼 입력된다.
0 1 1 1
1 0 0 0
1 0 0 0
0 0 0 0
dp[i][j]에 대해서
1) 기존의 board[i][j]의 값이 0이라면 자신은 정사각형에 포함될수 없으므로
dp[i][j]=0이다.
2) dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 중에 0이 있을경우에는 길이가 1보다 큰 정사각형을 만들수가 없으므로 dp[i][j]=1이다.
3) dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 가 모두 같은 값이면 dp[i][j]를 포함하여 길이가 1이더 긴 정사각형을 만들 수 있다. 그래서 dp[i][j]는 dp[i-1][j-1]의 제곱근의 +1 한값의 제곱이다.
ex) dp[i-1][j-1]=4 이면 실제 dp[i-1][j-1]은 길이가 2인 정사각형이므로 dp[i][j]는 길이가 3인 정사각형이 된다. 그래서 dp[i][j]=9가된다.
4) 나머지 경우는 dp[i-1][j-1], dp[i-1][j], dp[i][j-1] 가 모두 같지는 않지만 0도 아닌경우이다. 이경우에 정사각형의 길이는 가장 짧은 길이 + 1의 값을 가진다.
ex) 1,4,9의 값을 가지고 있는 경우 길이는 가장짧은 1의 값에 +1 한것이 되어 dp[i][j]=4이다.
for(int i=1; i<dp.length;i++){
for(int j=1; j<dp[0].length; j++){
if(board[i][j]==0){
// System.out.println("if문 : "+i+" "+j);
dp[i][j]=0;
}else if(dp[i-1][j-1]==0 || dp[i-1][j]==0 || dp[i][j-1]==0){
// System.out.println("else if문1 : "+i+" "+j);
dp[i][j]=1;
//System.out.println(Arrays.deepToString(dp));
}else if(dp[i-1][j-1]==dp[i-1][j] && dp[i-1][j]==dp[i][j-1]){
// System.out.println("else if문2 : "+i+" "+j);
dp[i][j]= ((int)(Math.sqrt(dp[i-1][j-1]))+1 )*((int)(Math.sqrt(dp[i-1][j-1]))+1);
}else{
// System.out.println("else 문 : "+i+" "+j);
int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
dp[i][j]= (int)(Math.sqrt(Math.min(min,dp[i][j-1])))+1;
dp[i][j] = dp[i][j]*dp[i][j];
}
answer=Math.max(answer,dp[i][j]);
//System.out.println(Arrays.deepToString(dp));
}
}코드
import java.util.*;
class Solution{
public int solution(int [][]board){
int answer = 0;
int sum = 0;
int [][] dp = new int[board.length][board[0].length];
for(int i=0; i<board.length; i++){
dp[i][0] = board[i][0];
sum+=dp[i][0];
}
for(int i=0; i<board[0].length; i++){
dp[0][i]=board[0][i];
sum+=dp[0][i];
}
if(sum>0){
answer=1;
}
//System.out.println(Arrays.deepToString(dp));
for(int i=1; i<dp.length;i++){
for(int j=1; j<dp[0].length; j++){
if(board[i][j]==0){
// System.out.println("if문 : "+i+" "+j);
dp[i][j]=0;
}else if(dp[i-1][j-1]==0 || dp[i-1][j]==0 || dp[i][j-1]==0){
// System.out.println("else if문1 : "+i+" "+j);
dp[i][j]=1;
//System.out.println(Arrays.deepToString(dp));
}else if(dp[i-1][j-1]==dp[i-1][j] && dp[i-1][j]==dp[i][j-1]){
// System.out.println("else if문2 : "+i+" "+j);
dp[i][j]= ((int)(Math.sqrt(dp[i-1][j-1]))+1 )*((int)(Math.sqrt(dp[i-1][j-1]))+1);
}else{
// System.out.println("else 문 : "+i+" "+j);
int min = Math.min(dp[i-1][j-1],dp[i-1][j]);
dp[i][j]= (int)(Math.sqrt(Math.min(min,dp[i][j-1])))+1;
dp[i][j] = dp[i][j]*dp[i][j];
}
answer=Math.max(answer,dp[i][j]);
//System.out.println(Arrays.deepToString(dp));
}
}
// System.out.println(Arrays.deepToString(dp));
return answer;
}
}