[Programmers]가장 큰 정사각형 찾기/JS

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/12905#

프로그래머스

---

접근방법

정답부터 말하자면 이 문제는 DP문제이다(난 몰랐음)

배열을 다 돌면서 확인해야되나? DFS인가? 혼자 고민고민하다가

뭔가 정해진 풀이가 있을 거 같아서 구글링해봤다 

원래같았으면 몇시간동안 이리저리 풀어봤을텐데 뭔가 삘이 왔어 내가 못풀거라는 삘..

DP란 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용하는 방식이다. 

반복문을 돌면서 이전에 구해놓은 길이와 비교하면서 답을 갱신해나가는 방식이라고 보면 된다.

 

첫번째 코드

function solution(board)
{
    var answer = 1;
    let row = board.length;
    let col = board[0].length;
    for(let j=1;j<col;j++){
        for(let i=1;i<row;i++){
            if(board[i][j]!=0 && board[i][j-1]!=0 && board[i-1][j]!=0 && board[i-1][j-1]!=0){
                board[i][j] = Math.min(board[i][j-1],board[i-1][j],board[i-1][j-1])+1;
                answer = Math.max(answer,board[i][j]);
            }
        }
    }

    return answer*answer;
}

행과 열을 인덱스 1부터 확인한다. (1부터 확인했다는 사실을 잊었었다..)

board[i][j]를 기준으로 왼쪽(board[i][j-1]), 위(board[i-1][j]), 위에서 왼쪽(board[i-1][j-1])의 값을 확인하고

이 값들이 모두 0이 아니라면 

3개의 값들 중에 가장 작은 값을 찾아서 +1을 해준 값을 board[i][j]에 저장해준다.

그 후, answer에 answer과 board[i][j]를 비교해서 큰 값을 저장해준다.

실패 ㅎㅎ

테스트 8 -> 전부 0인 경우라길래 아래 코드처럼 수정했다.

 

두번째 코드

function solution(board)
{
    var answer = 0;
    
    let row = board.length;
    let col = board[0].length;
    
    for(let j=1;j<col;j++){
        for(let i=1;i<row;i++){
            if(board[i][j]!=0 && board[i][j-1]!=0 && board[i-1][j]!=0 && board[i-1][j-1]!=0){
                board[i][j] = Math.min(board[i][j-1],board[i-1][j],board[i-1][j-1])+1;
                answer = Math.max(answer,board[i][j]);
            }
        }
    }

    return answer*answer;
}

모두 0인 경우를 고려해주려고

초기 answer의 값을 0으로 설정해줬다.

테스트 8은 통과했는데

잘 돌아가던 테스트 1, 테스트 6이 갑자기 실패가 뜬다..

뭐가 문제일까 내 코드를 다시 보니까

인덱스를 1부터 비교해줬던 것을 보았다.

board = [[0,1],[0,0]]이 입력되면 1이 나와야 되는데

위의 코드대로라면 0이 출력되는데 이게 문제라고 생각해서 고쳐봤다.

정답 코드

function solution(board)
{
    var answer = 0;
    
    let row = board.length;
    let col = board[0].length;
    
    if(board[0][0]==1 || board[0][1]==1 || board[1][0]==1) answer=1;
    
    for(let j=1;j<col;j++){
        for(let i=1;i<row;i++){
            if(board[i][j]!=0 && board[i][j-1]!=0 && board[i-1][j]!=0 && board[i-1][j-1]!=0){
                board[i][j] = Math.min(board[i][j-1],board[i-1][j],board[i-1][j-1])+1;
                answer = Math.max(board[i][j],answer);

            }
        }
    }
    return answer*answer;
}

아래의 for문에서 행=1, 열=1부터 조건을 검사하니까

board[0][0], board[0][1], board[1][0]만 검사해주면 된다.

위의 인덱스들이 1이라면 넓이가 1인 정사각형이 존재하는 경우에 해당하므로

answer에 1을 저장해주면 된다.

통과!!

조건을 잘 생각하자 헤헷0_<