알고리즘🅰/프로그래머스

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

개발조각 2022. 5. 10. 11:28
728x90
반응형

이번 문제는 풀다가 포기하고 질문하기에 도움을 받고 풀었습니다.

다들 천재입니다👍

 

접근방식

이 문제는 가장 큰 정사각형을 찾는 문제입니다.

2차원 배열에서

1 1
1 1

이렇게 있으면 가로 세로 길이가 2인 정사각형이 있다는 거고

1 1 1
1 1 1
1 1 1

이렇게 있으면 가로 세로 길이가 3인 정사각형이 있다는 겁니다.

 

 

테스트 1로 설명을 하자면

board = [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]

0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0

만약 여기서 길이가 2인 정사각형이 있는지 확인을 하려면

board[row][col] = 1이야 되고

board[row-1][col]

board[row][col-1]

board[row-1][col-1]

이 다 1이야 됩니다.

 

밑에 3개

board[row-1][col]

board[row][col-1]

board[row-1][col-1]

가 가능하게 하려면 row, col이 0일 경우 오류가 나옵니다.

 

그래서 먼저 row, col이 0인 경우를 제외하고 board[row][col] = 1인 경우를 찾은 후

board[row-1][col]

board[row][col-1]

board[row-1][col-1]

을 구하면 됩니다.

 

이 구한 값으로 어떻게 가장 긴 정사각형의 길이를 어떻게 구하냐면

이미지를 보시면 쉽게 이해하실 수 있습니다.

 

이 이미지를 보시면

노랑 : board[row][col]이 1인 값

주황, 초록, 하늘 : board[row][col]기준으로 board[row-1][col], board[row][col-1], board[row-1][col-1]값

빨강 글씨 : 주황, 초록, 하늘의 3가지 수 중에서 가장 작은 값 +1

 

이미지를 를 보시면

board[row][col]=== 1이면

board[row][col]을 기준으로  board[row-1][col], board[row][col-1], board[row-1][col-1]값을 구하고

3개의 값 중에서 가장 작은 값에 +1을 해준 뒤 board[row][col]에 넣어주었습니다.

 

그러면 board[row][col]이 1일 경우

board[row-1][col], board[row][col-1], board[row-1][col-1]중 하나가 0이면 이 정사각형은 2가 될 수 없습니다.

board[row-1][col], board[row][col-1], board[row-1][col-1]중 하나가 1이면 이 정사각형은 2가 됩니다.

 

board[row][col]가 2로 바뀐 값에 board[row-1][col], board[row][col-1], board[row-1][col-1]에서 가장 작은 값이 2이면 3으로 교체해주면 됩니다.

즉 누적해서 값을 변화시켜주면 됩니다.

해결방안

function solution(board)
{   
    for(let row=1; row<board.length; row++){
        for(let col=1; col<board[0].length; col++){
            if(board[row][col] === 1){
                board[row][col] = Math.min(board[row-1][col], board[row][col-1], board[row-1][col-1])+1;
            }
        }
    }
    return Math.max(...board.map(a=> Math.max(...a)))**2;
}

해결방안 순서

  1. 중복 for문으로 조건에 따라 board[row][col]를 교체해 주기
  2. 바뀐 board 2차원 배열에서 가장 큰 수의 제곱 구하기

 

1단계. 중복 for문으로 조건에 따라 board[row][col]를 교체해 주기

for(let row=1; row<board.length; row++){
    for(let col=1; col<board[0].length; col++){
        if(board[row][col] === 1){
            board[row][col] = Math.min(board[row-1][col], board[row][col-1], board[row-1][col-1])+1;
        }
    }
}

접근방법에서 설명을 했지만 이번 문제는

board[row][col]가 1이면

board[row-1][col], board[row][col-1], board[row-1][col-1]값 중에서 가장 작은 값 +1을 해주는 문제입니다.

 

board[row-1][col], board[row][col-1], board[row-1][col-1]를 구하려면 row와 col이 0이면 안됩니다.

row와 col이 0이면 -1을 해주었을 때 -1이 되기 때문에 없는 값이 되어 오류가 나옵니다.

그래서 for문을 사용했을 때 0부터가 아닌 1부터 시작을 해주었습니다.

 

그럼 board[row][col]===1인 경우를 찾고

board[row][col]===1이면

board[row-1][col], board[row][col-1], board[row-1][col-1]값 중에서 가장 작은 값 +1을 해주고

그 값을 다시 board[row][col]에 담아 주면 됩니다. 

 

 

2단계. 바뀐 board 2차원 배열에서 가장 큰 수의 제곱 구하기

return Math.max(...board.map(a=> Math.max(...a)))**2;

이 문제는 정사각형의 길이를 구하는 문제가 아니라 넓이를 구하는 문제입니다.

정사각형 넓이는 길이 제곱을 해주면 됩니다.

 

1단계에서 board배열을 새롭게 바꾸어 주었습니다.

기존 board배열에서는 0과 1만 존재했지만

새롭게 바꾸어준 board배열에서는 0,1,2,3... 등 0과 1이 아닌 수도 있을 수도 있고 없을 수도 있습니다.

새롭게 바꾸어준 board배열에서 가장 큰 수를 찾으면 됩니다.

 

가장 큰 수를 찾고 싶지만 board배열은 2차원 배열이라 애매해집니다.

그래서 board[0], board[1]... 에서 최댓값을 구한 뒤

board[0], board[1]...의 최댓값을 모은 뒤 다시 그 값에서 최댓값을 구해주었습니다.

 

제곱은 Math.pow()을 사용하는 방법도 있지만 간단하게 **을 사용해주는 방법도 있습니다.

  • Math.pow(7, 3) : 7의 3제곱
  • 7 ** 3 : 7의 3제곱

여기까지 프로그래머스 가장 큰 정사각형 찾기 해결방안에 대해 설명해보았습니다.

728x90
반응형