31. 가장 큰 정사각형 찾기 (Level 4, JavaScript)

가장 큰 정사각형 찾기 (Level 4)

문제

어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다.

A를 3만큼 밀면 D가 되고 z를 1만큼 밀면 a가 됩니다. 공백은 수정하지 않습니다.

보낼 문자열 s와 얼마나 밀지 알려주는 n을 입력받아 암호문을 만드는 ceasar 함수를 완성해 보세요.

• “a B z”,4를 입력받았다면 “e F d”를 리턴합니다.

풀이

function findLargestSquare(board) {
  let max = 0;
    for ( let i = 0; i < board[0].length; i++) {
      for ( let j = 0; j < board.length; j++ ) {
        board[i][j] = board[i][j] == "O" ? 1 : 0
      }
  }
  for ( let x = 1; x < board[0].length; x++ ) {
    for ( let y = 1; y < board.length; y++ ) {
      if ( board[x][y] !=0 ) {
        board[x][y] = 1 + Math.min(board[x-1][y], board[x][y-1], board[x-1][y-1])
      }
      if ( max < board[x][y] ) {
        max = board[x][y]
      }
    }
  }
  return Math.pow(max, 2)
}

//아래 코드는 테스트를 위한 출력 코드 입니다.
var testBoard = [['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']];
console.log(findLargestSquare(testBoard));

문제보고 주변 컴공인들에게 물어보니 그냥 DP로 풀면 되네! 라고 들어서 엄청 찾아봤는데도 접근도 어려운데다가 막상 써놓고 나서도 너무 복잡하다 생각들었는데, 다른사람들 코드가 더길어서 흐뭇했다(ㅋㅋ~)

BOJ 1915번과도 동일한 문제이다.

우선 첫 번째 for문에서는 O 표시를 1 X 표시를 0으로 바꿔준다.

두 번째 for문에서는 원소가 0이 아닌것에 대해서 왼쪽,위쪽, 왼쪽위쪽 세개 값중 최솟값에 1을 더해 만들수 있는 최대 변의 길이를 적어주고, 그 값이 max보다 크다면 max에 대입하는 식으로 해서, 최대 정사각형 변의 길이를 구한 후에 제곱해 리턴!

다른 사람의 풀이

더 좋은코드가 있을수도 있겠지만, 이것보다 더 긴 코드는 읽고싶지 않다..