Ex)
board 배열
board | 0열 | 1열 | 2열 | 3열 | 4열 | 5열 | 6열 |
---|---|---|---|---|---|---|---|
0행 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1행 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
2행 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
horizon 배열 : horizon[i][j] -> (왼쪽방향으로) 세로길이가 1이고 가로길이가 horizon[i][j]인 직사각형을 만들 수 있음을 의미하게 된다.
horizon | 0열 | 1열 | 2열 | 3열 | 4열 | 5열 | 6열 |
---|---|---|---|---|---|---|---|
0행 | 0 | 1 | 2 | 3 | 4 | 0 | 0 |
1행 | 0 | 0 | 1 | 2 | 3 | 0 | 1 |
2행 | 0 | 0 | 1 | 2 | 3 | 0 | 0 |
(1) 순차적으로 horizon 값을 확인한다. 만일 horizon값이 n보다 클 경우 더 큰 정사각형을 찾을 수 있으므로 다음을 수행한다
while (temp > n) {
- 확인하려고 하는 horizon 위치가 테이블 범위를 초과하지 않는지 확인한다. 초과할 경우 루프를 빠져나간다.
- 만일 horizon[i+cnt][j]가 temp보다 작을 경우 확인해야할 정사각형의 크기가 줄어듦을 의미하므로 temp 값을 horizon[i+cnt][j]로 수정한다.
- cnt를 1 증가시킨다
- 만일 cnt==temp 인 경우, 한 변의 길이가 temp인 정사각형을 만들 수 있는 것을 의미하므로 n 값을 업데이트하고 루프를 빠져나간다.
}
public int solution(int [][]board) {
int answer = 0;
int n = 0; int temp = 0;
int k = 0;
int[][] horizon = new int[board.length][board[0].length]; //가로로 연속되는 1의 개수를 저장
int cnt = 0;
//가로로 연속되는 1의 개수를 구한다
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
if(j == 0) {
if(board[i][j] == 1) { horizon[i][j] = 1; }
} else {
if(board[i][j] == 1) {
horizon[i][j] = horizon[i][j-1] + 1;
}
}
}
}
//아래로 내려가면서 정사각형 만들 수 있으면 한 변의 최대 길이로 업데이트한다
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
if(horizon[i][j] > n) { //현재까지 구한 가장 긴 한변의 길이보다 값이 더 클 경우 확인한다
temp = horizon[i][j]; //temp : 정사각형 한 변의 길이
if(temp == 1) { if(temp > n) { n = temp; continue;}}
cnt = 1; //값을 확인한 개수
if(i + temp - 1 >= board.length) { temp = board.length - i; } //*****이거추가안하면 효율성 테스트 하나 통과 못함
while(temp > n) {
if(i+cnt < board.length) { //범위 이내에서만 확인
if(horizon[i+cnt][j] < temp) { //정사각형 한 변의 길이를 줄여야 할 경우
temp = horizon[i+cnt][j];
}
cnt++;
if(cnt == temp) { //만들려는 정사각형을 다 만들면 최대 변의 길이 업데이트하고 break
if(n < temp) { n = temp; }
break;
}
} else { break; }
} //end while
}
}
}
answer = n * n;
return answer;
}
효율성 테스트 통과가 어려웠다. (겁나 까다롭게 느껴졌음)
1) 탐색 범위를 줄일 방법을 생각하지 못해서 효율성 TC 3개를 모두 통과하지 못함.
2) horizon 배열을 사용해 탐색 범위를 줄여보고자 했지만 효율성 TC 3개를 모두 통과하지 못함
3) horizon 값이 1이상일 경우 모두 탐색하던 것을, horizon값이 n(현재까지 구한 정사각형 한 변의 최대 길이)보다 클때만 탐색하는 것으로 수정함. 하지만 효율성 TC 1개를 통과하지 못함.
4) while루프를 돌기 전, 미리 탐색 범위를 줄이는 코드를 삽입해 효율성 TC를 모두 pass함.
if(i + temp - 1 >= board.length) { temp = board.length - i; }