프로그래머스 Lv3 몸짱 트레이너

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

프로그래머스

1. 헬스장의 예약 내역이 주어졌을때, 구현을 통해서 구하는 것이 아닌, 회원수가 최대인 구간만 구하게 되면 나머지는 회원수가 최대인 시간의 배열의 부분 집합으로 구할 수 있습니다.

2. priority_queue를 사용하여, 그리디하게 회원수가 최대인 시간을 구해주었으며,

3. 문제의 핵심인 락커의 위치를 구할떄는 락커의 각 부분배열을 완전탐색으로 구해주어, 시간내에 문제를 해결할 수 있었습니다.

 

그리디를 사용한 구간이 곂치는 회원수를 구하는 방법

• 시간을 오름차순으로 정렬한다.
• 큐를 오름차순으로 생성하고, 예약이 끝나는 시간을 넣어준다.
• 다음 순서부터 예약 시작 시간이 우선순위 큐의 최솟값보다 클 때 pop()을한다.
• 아래와 같은 예약시간이 있다면

• 정확하게 앞에 있는 예약시간이 저장되는 것은 아니지만, 예약시간이 겹쳐지는 구간은 구해지는 것을 확인 할 수있다.

int getMaxUser(vector<vector<int>> timetable)
{
    sort(begin(timetable), end(timetable));
    
    priority_queue<int, vector<int>, greater<int>> pq_less;
    pq_less.push(timetable[0][1]);
    
    for(int i = 1; i < timetable.size(); ++i)
    {
        pq_less.push(timetable[i][1]);
        if(pq_less.top() < timetable[i][0])
        {
            pq_less.pop();
        }
    }
    return pq_less.size();
}

예약자가 한명이면 거리는 0으로 처리했다.

if(maxCrowded == 1) return 0;

가장 먼 거리는 대각선의 경우로 시작 위치를 제외한 (나머지 대각선 칸 * 2)로 계산했다.

    for(int distance = (n - 1) * 2; distance > 0; distance--)
    {

빨간색 테두리에 점이 있어야지 거리가 최대가 되므로 x 또는 y가 0일 때만 반복문을 진행했다.

for(int y = 0; y < n; ++y)
{
    for(int x = 0; x < n; ++x)
    {
        //x와 y가 선에 겹쳐있지 않을 때, 무조건 선에 있어야 유리하므로 해당 x,y배제
        if(x != 0 && y != 0) continue;

해당 포인트를 vector<pair<int, int>>에 넣어주고

vector<pair<int, int>> people{{x, y}};

0,0에서부터 탐색을 시작했으므로 같은 y축 테두리에 있거나 x2가 x보다 작거나 같으면 탐색을 진행하지 않았다.

for(int y2 = y; y2 < n; ++y2)
{
    for(int x2 = 0; x2 < n; ++x2)
    {
        if(y2 == y && x2 <= x) continue;

y2, x2의 위치가 최대 거리를 만족한다면 people에 넣어준다.

if(canPlaceFurther({y2, x2}, distance, people))
{
    people.push_back({y2, x2});
}

아래는 canPlaceFurther 함수인데, people을 순회하면서 현재 들어온 위치가 최대거리 조건을 만족하는지 확인하는 함수이다.

bool canPlaceFurther(pair<int, int> coord, int maxDistance, vector<pair<int, int>>& people)
{
    for(pair<int, int>& p : people)
    {
        if(getDistance(p, coord) < maxDistance)
        {
            return false;
        }
    }
    return true;
}

문제의 조건에 맞도록 짠 거리 구하는 함수

int getDistance(pair<int, int> a, pair<int, int> b)
{
    return abs(a.first - b.first) + abs(a.second - b.second);
}

완전 탐색을 통해서 최대 예약 가능한 사람과 people의 크기가 같다면 현재 거리를 반환한다.

                    if(people.size() == maxCrowded)
                        return distance;
                    }

전체코드

#include <vector>
#include <algorithm>
#include <climits>
#include <queue>

using namespace std;

const int MAX = 1000 + 1;

int getDistance(pair<int, int> a, pair<int, int> b)
{
    return abs(a.first - b.first) + abs(a.second - b.second);
}

bool canPlaceFurther(pair<int, int> coord, int maxDistance, vector<pair<int, int>>& people)
{
    for(pair<int, int>& p : people)
    {
        if(getDistance(p, coord) < maxDistance)
        {
            return false;
        }
    }
    return true;
}

int getMaxUser(vector<vector<int>> timetable)
{
    sort(begin(timetable), end(timetable));
    
    priority_queue<int, vector<int>, greater<int>> pq_less;
    pq_less.push(timetable[0][1]);
    
    for(int i = 1; i < timetable.size(); ++i)
    {
        pq_less.push(timetable[i][1]);
        if(pq_less.top() < timetable[i][0])
        {
            pq_less.pop();
        }
    }
    return pq_less.size();
}
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) 
{
    int answer = 0;
    int numberOfPeople[MAX] = {0,};
    int start = INT_MAX;
    int end = 0;
    
    int maxCrowded = getMaxUser(timetable);
    if(maxCrowded == 1) return 0;
    
    for(int distance = (n - 1) * 2; distance > 0; distance--)
    {
        for(int y = 0; y < n; ++y)
        {
            for(int x = 0; x < n; ++x)
            {
                //x와 y가 선에 겹쳐있지 않을 때, 무조건 선에 있어야 유리하므로 해당 x,y배제
                if(x != 0 && y != 0) continue;
                
                vector<pair<int, int>> people{{x, y}};
                
                for(int y2 = y; y2 < n; ++y2)
                {
                    for(int x2 = 0; x2 < n; ++x2)
                    {
                        if(y2 == y && x2 <= x) continue;
                        
                    if(canPlaceFurther({y2, x2}, distance, people))
                    {
                        people.push_back({y2, x2});
                    }
                    
                    if(people.size() == maxCrowded)
                        return distance;
                    }
                }
            }
        }
    }
    return answer;
}