프로그래머스 - [PCCE 기출문제] 10번 / 공원 C++

오늘은 이전 포스팅 2024.11.17 - [알고리즘/프로그래머스] - 프로그래머스 - [PCCE 기출문제] 9번 / 지폐 접기 C++

에 이어 10번 문제를 풀어보았다. 개인적으로 PCCE 중에 개발자 직무를 지원할 때 간단하게 코딩테스트 문제로도 나올 수 있는 문제라고 생각이 들었다. 물론 어려운 문제에 해당하지는 않고, 간단한 사고방식을 알 수 있는 문제로 나오지 않을까 생각이 든다.

 

알고리즘 난이도 및 시간 ( ※ 개인적인 의견 )

• 난이도 : Level 2.5 ( ※ Min : 0, Max : 10 )
• 풀이 시간 : 15분
• 제출 횟수 : 1번 
• 풀이 결과 : Pass

---

문제 설명

 지민이가 여러 개의 돗자리를 가지고 있는데, 공원에서 넓게 놀고 싶은데 다른 사람의 영역을 침범하지 않으면서 가장 넓게 사용할 수 있는 돗자리를 구하는 문제다. 특이한 점은 돗자리는 정사각형이라는 것이다. 그 이외에는 큰 어려움은 없다.

출처 : 프로그래머스

 

 제한사항에서 특이사항은 공원이 크기가 최대 50 * 50이라는 점 이외에는 없다.

출처 : 프로그래머스

---

문제풀이

 나는 문제를 보자마자, 공원이라는 2차원 배열 공간을 만들고 다른 사람이 사용하지 않는 공간 중 가장 큰 정사각형을 찾은 후 지민이가 가지고 있는 돗자리 중 가장 큰 길이를 찾아야겠다는 생각을 했다. 즉 빈 공간이 있다면 해당 지점을 기반으로 사각형 형태로 다 Check 하는 로직을 구현했다. 딱히 어려운 문제도 아니고 다 Check 한다고 해서 시간이 오래 소요될 것 같지가 않아서 아래와 같이 구현했다. 함수별로 기능 동작을 설명하도록 하겠다.

 

• SetPossibleSpace : 전달받은 문자열을 비교하여 -1인 경우 내가 돗자리를 깔 수 있다는 것을 인지하기 위해 2차원 배열에 방문 가능 여부를 설정하는 함수다.
• IsPossibleSqure : 전달받은 시작점 좌표와 길이를 이용하여 iSize 변의 길이가 전부 돗자리를 필수 있는 영역인지 확인하는 함수다.
• GetPossibleMaxSize : IsPossibleSqure를 이용하여 Size를 하나씩 늘려가면서 가능한 가장 큰 변의 길이를 찾는 함수다. 
• GetAnswer : GetPossibleMaxSize를 통해 공원에서 돗자리를 펼 수 있는 가장 큰 변의 길이를 가지고, 우리가 가지고 있는 돗자리 길이를 확인하면서 GetPossibleMaxSize에서 반환한 변보다 작거나 같은 값 중 가장 큰 값을 구하는 함수다.
• solution : 위의 함수들을 활용하여 Control 하는 main 함수다.

#include <string>
#include <string.h>
#include <vector>

using namespace std;

const int MAX_PARK_SIZE = 51;

bool bIsPossibleSpace[MAX_PARK_SIZE][MAX_PARK_SIZE];

void SetPossibleSpace(const vector<vector<string>>& rPark)
{
    int iArrayYSize = static_cast<int>(rPark.size());
    for (int iY = 0; iY < iArrayYSize; ++iY)
    {
        int iArrayXSize = static_cast<int>(rPark[iY].size());
        for (int iX = 0; iX < iArrayXSize; ++iX)
        {
            if ("-1" == rPark[iY][iX])
            {
                bIsPossibleSpace[iY][iX] = true;
            }
        }
    }
}

bool IsPossibleSqure(const int& rX, const int& rY, const int& iSize)
{
    bool bIsPossible = true;

    for (int iX = rX; iX <= rX + iSize; ++iX)
    {
        for (int iY = rY; iY <= rY + iSize; ++iY)
        {
            if (false == bIsPossibleSpace[iY][iX])
            {
                bIsPossible = false;
            }
        }
    }

    return bIsPossible;
}

int GetPossibleMaxSize(const int& rXSize, const int& rYSize)
{
    int iTemp = 0;
    int iMaxSize = -1;
    for (int iY = 0; iY < rYSize; ++iY)
    {
        for (int iX = 0; iX < rXSize; ++iX)
        {
            if (true == bIsPossibleSpace[iY][iX])
            {
                iTemp = 1;
                while (true == IsPossibleSqure(iX, iY, iTemp - 1))
                {
                    iTemp++;
                }
                // 대각선으로 확인을 진행하면됨
                if (iTemp - 1 > iMaxSize)
                {
                   iMaxSize = iTemp - 1;
                }
            }
        }
    }
    return iMaxSize;
}

int GetAnswer(const int& rMaxSize, const vector<int>& rMats)
{
    int iAnswer = -1;
    int iCount = static_cast<int>(rMats.size());

    for (int i = 0; i < iCount; ++i)
    {
        if (rMats[i] <= rMaxSize)
        {
            if (iAnswer <= rMats[i])
            {
                iAnswer = rMats[i];
            }
        }
    }

    return iAnswer;
}

int solution(vector<int> mats, vector<vector<string>> park) {
    memset(bIsPossibleSpace, 0, sizeof(bIsPossibleSpace));

    SetPossibleSpace(park);
    int xSize = static_cast<int>(park[0].size());
    int ySize = static_cast<int>(park.size());
    int iMaxSize = GetPossibleMaxSize(xSize, ySize);
    int answer = GetAnswer(iMaxSize, mats);
    return answer;
}

---

결과

문제 링크 : 코딩테스트 연습 - [PCCE 기출문제] 10번 / 공원 | 프로그래머스 스쿨

프로그래머스

 

 해당 포스팅을 기반으로 PCCE 기출문제 시리즈는 모두 풀이완료 하였다. 다음 포스팅은 조금 더 어려운 문제를 가지고 풀이할 수 있도록 하겠다. 다들 날씨가 추운데 감기 걸리지 않게 따듯하게 입고 다니길 바란다.