알고리즘 - (가장 큰 정사각형 찾기)

aquarius1997·2020년 5월 20일
0

Algorithm

목록 보기
4/9
  • 문제 출처 : 프로그래머스
  • 문제명 : 가장 큰 정사각형 찾기
  • 분류 : 연습문제
  • 언어 : Java
  • 체감 난이도 : ⭐⭐⭐⭐⭐
  • 풀이 시간 : 2h~
  • Fail Cnt : 4
  • 효율성 테스트 통과가 까다롭게 느껴진 문제

1. 프로세스

1) 입력으로 받은 테이블(board[][])에 대해 수평으로 1이 연속되는 개수를 저장하는 테이블(horizon[][])을 만든다.

Ex)
board 배열

board0열1열2열3열4열5열6열
0행0111100
1행0011101
2행0011100

horizon 배열 : horizon[i][j] -> (왼쪽방향으로) 세로길이가 1이고 가로길이가 horizon[i][j]인 직사각형을 만들 수 있음을 의미하게 된다.

horizon0열1열2열3열4열5열6열
0행0123400
1행0012301
2행0012300

2) horizon 배열을 이용해서, 제일 큰 정사각형을 찾는다

  • n : 가장 긴 정사각형의 한 변의 길이를 저장

(1) 순차적으로 horizon 값을 확인한다. 만일 horizon값이 n보다 클 경우 더 큰 정사각형을 찾을 수 있으므로 다음을 수행한다

  • temp에 현재 horizon[i][j] 값을 저장한다. 즉, temp는 구하고 싶은 정사각형의 한 변의 길이를 저장한다
  • 만일 temp가 1일 경우 n에 temp를 저장하고 continue;를 수행해 다음 과정을 수행하지 않는다.
  • (현재 행 위치[=i] + temp) 가 테이블의 (세로)범위를 초과하면 temp를 (테이블 세로 크기 - 현재 행 위치[=i]) 로 조정한다.
  • temp가 n보다 클 경우에만 while 루프를 돌며 temp 길이만큼 정사각형을 만들 수 있는지 확인한다.
    루프는 현재 위치(행:i, 열:j)를 기준으로, 아래 방향의 값만(horizon[i+cnt][j], 1<cnt<temp) 확인한다.

while (temp > n) {

  • 확인하려고 하는 horizon 위치가 테이블 범위를 초과하지 않는지 확인한다. 초과할 경우 루프를 빠져나간다.
  • 만일 horizon[i+cnt][j]가 temp보다 작을 경우 확인해야할 정사각형의 크기가 줄어듦을 의미하므로 temp 값을 horizon[i+cnt][j]로 수정한다.
  • cnt를 1 증가시킨다
  • 만일 cnt==temp 인 경우, 한 변의 길이가 temp인 정사각형을 만들 수 있는 것을 의미하므로 n 값을 업데이트하고 루프를 빠져나간다.
    }

3) 정사각형의 크기를 구해서 리턴한다. (크기 = n * n)


2. 구현 코드

    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;
    }

3. Fail 이유

효율성 테스트 통과가 어려웠다. (겁나 까다롭게 느껴졌음)

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; } 
profile
안녕하세요😀😀

0개의 댓글