Lv2_[가장 큰 정사각형 찾기, C++] 풀이 및 알고리즘 정리 - 프로그래머스

 

프로그래머스

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

알고리즘

• 정사각형을 찾기 위해 선택 index 기준으로 차근차근 알아보는 방법을 선택

주어진 2차원 벡터를 행렬형태로 배치하고 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]]

2차원 벡터 행렬로 표현

 

• index기준(1인 경우)으로 '왼쪽 대각선 위', '왼쪽', '위쪽' 3부분을 비교함
• 비교 후 가장 값이 낮은 값과 현재 index 값을 더해줌 (위 결과 값은 정사각형이 만족되는 크기임)
• index가 x축(행), y축(열) 둘 중에 1개라도 0이 포함되는 곳은 최대 크기가 무조건 1이 됨
• 1의 값을 가진 index가 존재한다면 다른 부분을 확인하지 않고 index(1,1)부터 시작하게 만듦(불필요한 연산 방지)

- index(1,1) 기준으로 보면
  [0, 1, 1] 값이 나오고 가장 낮은 값은 0
  그렇기 때문에 index(1,1)은 정사각형 0 + 1 = 1이므로 정사각형의 크기는 1이됨

(1, 1) 비교

위의 기준으로 index(1, 2) [1, 1, 1] 값이 나오기 때문에 1 + 1 = 2 가 됩니다.

(1, 2) 비교

이러한 과정을 끝까지 반복하면 본인 index에서 정사각형을 만족시킬 수 있는 값을 출력할 수 있음

 비교 과정

비교 결과

 

계산이 끝났으면 가장 큰 값 3을 찾을 수 있음

문제의 결과는 제곱(면적)을 반환 해주면 되기 때문에 3 * 3 = 9를 리턴해주면 완료!

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(vector<vector<int>> board) {
    int answer = 0;
    int x_start = 0;
    int y_start = 0;
 
    for (int i = x_start; i < board.size(); i++) {
        for (int k = y_start; k < board[i].size(); k++)    {
            if (board[i][k] != 0) {
                if (i == 0 || k == 0) {
                    if (board[i][k] > answer) {
                        answer = board[i][k];
 
                        x_start = 1;
                        y_start = 1;
                    }
                } else {
                    // (x-1, y-1), (x-1, y), (x, y-1)
                    int compare[3] = { board[i-1][k-1], board[i-1][k], board[i][k-1] };
                    int min_value = *min_element(compare + 0, compare + 3);
                    board[i][k] += min_value;
 
                    if (board[i][k] > answer) {
                        answer = board[i][k];
                    }
                }
            }
        }
    }
 
    return (answer * answer);
}

 

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓