[프로그래머스] Level 1. 공원

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

프로그래머스

 

다른사람들과는 조금 다른방법으로 문제를 푼 것 같다.

• 입력받은 매트 길이를 내림차순으로 정렬한다.
• isMat() 함수를 이용해 해당 매트가 공원에 들어갈 수 있는지를 검사하여, true가 나올 경우 매트 사이즈를 반환한다.

• 가로열을 하나씩 검사한다.  (i,j) 위치에서, 해당 자리가 비어있다면 그 자리에서 세로로 매트길이만큼 검사한다. (1,0)에서 매트길이 3을 검사할 경우, (1,0)(2,0)(3,0) 을 검사한다.
• 만약 (i,j) 위치에서 세로로 매트길이만큼 모두 비어있다면, 다음 j로 넘어가서 계산을 계속한다. 검사중 한번이라도 실패하면 startJ를 다시 설정한다. 
• startJ 로부터 공원끝자락까지 길이를 계산했을때, 남은 공원 길이가 매트길이보다 적다면 어차피 i행은 실패이므로 다음 행으로 넘어간다 (break)
• 검사를 마쳣을때 startJ 부터 현재 j위치의 길이가 매트길이와 같다면 매트가 공원에 들어갈 수 있다는 의미이므로, 더이상 검사하지 않고 true를 반환한다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool check_column(const vector<vector<string>>& park , int col, int row, int mat_size ){
    bool valid =- true;
    int col_size = park.size();
    for(int i = 0; i<mat_size; i++){
         if(col_size <= col+i || park[col+i][row] != "-1")
        {
            valid = false;
            break;
        }
    }
    
    return valid;
}

bool isMat(const vector<vector<string>>& park , int size){
    
    int col_size = park.size();
    int row_size = park[0].size();
    
     for(int i = 0 ; i<col_size; i++){
        int startJ = -1;
        for(int j = 0; j<row_size; j++){

            //남은 가로사이즈가 매트보다 작다면 더이상 검사하지 않음.
            int expected_start_j = startJ == -1 ? j : startJ;
            if(row_size - expected_start_j < size) break;  

            if(park[i][j] != "-1") {
                startJ = -1;
                continue;
            }

            //세로로 매트 사이즈만큼  비어있는지 확인
            bool ok_size = check_column(park,i,j,size);

            if(!ok_size){
                startJ = -1;
                continue;
            }

            //시작점 설정
            if(startJ == -1) startJ = j;
            if(j-startJ+1 == size) return true;

        }
    }
    return false;
}

int solution(vector<int> mats, vector<vector<string>> park) {

    sort(mats.rbegin(), mats.rend());
    
    for(int mat = 0; mat <mats.size(); mat++){
        if(isMat(park,mats[mat])) return mats[mat];
    }
    
    return -1;
}

 

 

마무리하며

다른 사람들과 좀 다른 방법으로 문제를 푼 것 같다. 다른 풀이는 이렇다.

• 2차 행렬을 선언하고, 인접한 매트를 깔 수 있으면 1로 설정한다. 
• 2중 for문으로 차례차례 돌면서, 1인 칸들에 대해 다음 검사를 수행한다.
• 자신의 왼쪽, 위쪽, 왼쪽대각선 값들 중 최솟값을 찾는다. 그 최솟값 + 자신의 값으로 값을 갱신한다.
• 해당 숫자는 "내 기준 왼쪽위로 매트를 펼칠 수 있는 최대사이즈" 를 의미한다.
• 행렬안에서 나오는 가장 큰수가 펼칠수 있는 가장 큰 매트 수이다.

for (int i = 0; i < park.size(); i++)
    {
        for (int j = 0; j < park[0].size(); j++)
        {
            if (park[i][j] == "-1")
            {
                dp[i+1][j+1] = 1;
            }
        }
    }

    for (int i = 1; i <= park.size(); i++)
    {
        for (int j = 1; j <= park[0].size(); j++)
        {
            if (dp[i][j] != 0)
            {
                dp[i][j] = min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                if (answer < dp[i][j])
                {
                    answer = dp[i][j];
                }
            }
        }
    }

 

이방법이 더좋은것같아.>! 그래도 나름 창의적인 방법으로 문제를 풀었다는 점에서 뿌듯함을 느낀다