가장 큰 정사각형을 찾는 문제

문제 출처 : http://tryhelloworld.co.kr/

 

x	o	o	o	x
x	o	o	o	o
x	x	o	o	o
x	x	o	o	o
x	x	x	x	x

 

o 표시가 되어있는 구역 중에 가장 큰 정사각형을 찾아서 칸수를 리턴한다.

 

//정답 9칸

x	o	o	o	x
x	o	o	o	o
x	x	o	o	o
x	x	o	o	o
x	x	x	x	x

 

 

//풀이 기준

- 모든 0 이 시작하는 부분에서 

오른쪽으로 0 이 연속되는 개수와

아랫쪽으로 0 이 연속되는 개수를 확인하여

두 수가 같거나 작은 쪽의 수를 리턴한다.

 

 

 

function findLargestSquare(board)

{

var answer = 0;

 

  var rowCount = board.length;

  var colCount = board[0].length;

  

  var rowIndex = 0;

  var colIndex = 0;

  

  for (;rowIndex < rowCount ; rowIndex++) {

    colIndex = 0;

    for (;colIndex < colCount ; colIndex++) {      

 

//o 이 시작되는 부분은 모두 찾는다.

      if (board[rowIndex][colIndex] == 'O'){

 

  //o 이 연속되는 곳의 정사각형 사이즈를 리턴한다.

        var result = SearchArray(rowIndex,colIndex,board);

 

   //가장 큰 사이즈인지 비교한다.

        if (result > answer){

          answer = result;

        }

      }

    }

  }

  

return answer * answer;

}

 

function SearchArray (_rowId, _colId, board) {

  var count = 0;

  

  var rightCount = board[_rowId].length - (_colId + 1);

  var downCount = board.length - (_rowId + 1);

  

  var dId = 0;

  var rId = 0;

  

  var rightContinueCount = 0;

  var downArr = new Array(rightCount);

 

  //오른쪽으로 이동하면서 가로의 연속개수를 확인

  for (rId = 0; rId <= rightCount ; rId++){

    if (board[_rowId][_colId + rId] == 'O'){

      rightContinueCount++;

      var downContineCount = 0;

 

//오른쪽으로 한칸 이동할때마다 아래쪽으로 연속개수 확인

      for (dId = 0; dId <= downCount ; dId++) {

            if (board[_rowId + dId][_colId + rId] == 'O'){

          downContineCount++;

          }else{

                  break;

          }

   }

 

//아래쪽 연속개수를 저장해둔다.

      downArr[rId] = downContineCount;

  }else{

//o가 아닌부분이 나오면 반복문 탈출

      break;

  }

  }

  

  var darrlength = 0;

  var minium = 999;

  //아래쪽 연속개수 중에 가장 작은 값을 찾는다.

  for (;darrlength < downArr.length ; darrlength++){

    if (minium > downArr[darrlength]){

      minium = downArr[darrlength];

    }

  }

  

  //아래쪽 연속 개수와 오른쪽 연속 개수를 비교하여 정사각형 크기를 리턴한다.

  if (rightContinueCount == minium){

    count = rightContinueCount;

  }else {

    if (rightContinueCount < minium){

      count = rightContinueCount;

    }else{

      count = minium;

    }

  }

    

  return count;

}

 

 

 

 

//좀더 효율적인 풀이기준이 있다면 조언 부탁드립니다~~