[C++] [PCCE 기출문제] 10번 / 공원

 

 

 

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

 

문제 3줄 요약

1. 공원에 정사각형 모양의 돗자리를 까려고 한다. (공원은 정사각형이 아닐 수 있다는 점!)

2. 공석은 "-1"로 표시되어 있다.

3. 사람들이 없는 곳에 돗자리를 펼치려고 하는데, 깔 수 있는 가장 큰 돗자리는?

 

---

 

문제를 읽고 바로 든 접근법은

완전탐색을 해보는 것이었다.

 

모든 좌표를 돌며

해당 좌표로부터 N×N 크기의 공간 안이

모두 "-1"인지 파악하는 방식을 생각하였고

 

공원의 길이가 최대 50

돗자리의 종류가 최대 10종류, 최대 길이 20의 제한사항을 고려해보았다.

 

 

(50 × 50)를 완전 탐색하며

길이가 20인 돗자리 10개를 탐색한다고 하면

2500 × 200 = 500000번의 연산 정도..

 

이 정도면 시간 초과는 안나겠다고 생각하였고

바로 FOR문 도배!!

 

int solution(vector<int> mats, vector<vector<string>> park) {
    sort(mats.begin(), mats.end());
    int answer = -1;
    
    for(int i=0; i<mats.size(); i++)
    {
        int n = mats[i];
        
        for(int h=0; h<park.size(); h++)
        {
            for(int w=0; w<park[0].size(); w++)
            {
                if(park[h][w] != "-1") continue;
                answer = max(answer, chk(park,h,w,n));
            }
        }
        if(answer==-1) return answer;
    }
    return answer;
}

 

돗자리 종류를 하나씩 골라서

공원의 (0,0) 좌표부터 끝까지 돌아보며

N×N 크기의 공석(= "-1")을 확인해보는 chk 함수를 실행한다.

 

chk 함수는 아래와 같다.

 

int chk(vector<vector<string>> park, int h, int w, int n)
{
    bool chk = true;
    for(int dx=0; dx<n; dx++){
        for(int dy=0; dy<n; dy++)
        {
            if(((h+dx)>=park.size() || (w+dy)>=park[0].size()) || \
               park[h+dx][w+dy]!="-1"){
                return -1;
            }
        }
    }
    return n;
}

 

 

한 자리라도 공석이 아니라면,

그 공간은 돗자리를 둘 수 없으니

바로 -1을 반환해준다.

 

chk 함수 구현 중

돗자리가 정사각형인건 인지했는데,

자연스레 공원도 정사각형이라고 생각하고 반복문을 돌리다가

배열의 인덱스 에러가 왜 나는지 한참을 고민했다... ㅋㅋ

 

 

추가적으로

solution 함수 부분에 돗자리 길이를 오름차순 정렬해주고

작은 길이의 돗자리가 -1로 배치가 불가하다면,

그 이후의 더 큰 돗자리들은 당연하게 배치할 수 없으니

바로 -1을 return 해주었다.

 

 

좌측은 정렬 및 For문 break ×

우측은 정렬 및 For문 break O

 

 

 

좌측이 미세하게 빠른 경우도 있지만,

테스트 6과 같은 케이스는 우측이 압도적으로 빠른 경우 또한 존재했다.

 

전체 코드는 아래와 같다.

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

using namespace std;

int chk(vector<vector<string>> park, int h, int w, int n)
{
    bool chk = true;
    for(int dx=0; dx<n; dx++){
        for(int dy=0; dy<n; dy++)
        {
            if(((h+dx)>=park.size() || (w+dy)>=park[0].size()) || \
               park[h+dx][w+dy]!="-1"){
                return -1;
            }
        }
    }
    return n;
}

int solution(vector<int> mats, vector<vector<string>> park) {
    sort(mats.begin(), mats.end());
    int answer = -1;
    
    for(int i=0; i<mats.size(); i++)
    {
        int n = mats[i];
        
        for(int h=0; h<park.size(); h++)
        {
            for(int w=0; w<park[0].size(); w++)
            {
                if(park[h][w] != "-1") continue;
                answer = max(answer, chk(park,h,w,n));
            }
        }
        if(answer==-1) return answer;
    }
    return answer;
}

 

---

 

For문이 많아서

코드가 조금 지저분해보이지만,,

나름 chk 함수도 따로 작성해뒀고 노력은 했다 ㅎㅎ..

 

끝!