[프로그래머스 level2] 가장 큰 정사각형 찾기

김예지·2021년 10월 22일
0

[알고리즘] 프로그래머스

목록 보기
89/102

문제

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

문제 풀이

코드

function solution(board)
{
    const x=board.length; 
    const y=board[0].length;
    let max=Number.MIN_SAFE_INTEGER;
    
    //제한사항(현대수학에서는 0도 자연수로 보는 경우도있음)
    if(x<=1 || y<=1){
        for(let i=0; i<x; i++){
            for(let j=0; j<y; j++){
                if(board[i][j]===1) return 1; //1이 하나라도 있는 경우
            }
        }
        return 0; //모두 0인경우  
    }
    
    //(1,1)부터
    for(let i=1; i<x; i++){
        for(let j=1; j<y; j++){
            if(board[i][j]>=1){
                const up=board[i-1][j];
                const upLeft=board[i-1][j-1];
                const left=board[i][j-1];
                const min=Math.min(up, upLeft, left)+1;
                board[i][j]=min;
                max=Math.max(max, min);
            }
            else max=Math.max(max, 0); //모두 0인경우를 고려
        }
    }
    return Math.pow(max, 2); //max**2
}
  • 풀이는 이분의 코드를 참고했다. 혼자서는 문제의 원리조차 도출해내기 힘들었다. 답을 보면서, 문제를 이해할 수 있었다. 지금은 혼자 풀지 못했지만, 다음에 비슷한 문제가 나오면 이 원리를 기억해낼수있으면 된다.
  • 제한사항을 잘 생각해내자! 코딩테스트에는 '히든테스트'라는 것이 존재한다. 이 히든테스트에서 살아남기 위해서는 '제한사항'을 잘 보면 된다는 꿀팁을 봤다.
    이 문제에서는 행과 열이 1일수도 있다는 것(그러면서도 모든 값이 0일수도있다는 것), 그리고 표의 모든 값이 0일수도 있다는 것을 고려해야한다.
    이문제처럼, 미리 제한사항에 해당하는 테케를 미리 집어넣고 문제를 푸는 것도 좋은 방법같다. 제한사항에 신경쓰자!

참고

profile
김예지
내가 짱이다 😎 매일 조금씩 성장하기🌱
이전 포스트

[프로그래머스 level2] 문자열 압축_카카오 2020

다음 포스트

[프로그래머스 level2] 모음 사전

0개의 댓글