[Algorithm] Programmers :: 몸짱 트레이너 라이언의 고민

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

프로그래머스

int getDistance(int y1, int x1, int y2, int x2)
{
    return abs(y2 - y1) + abs(x2 - x1);
}
 
bool canPlace(int y, int x, vector<vector<int>>& nodes, int distance)
{
    for (int i = 0; i < nodes.size(); ++i)
    {
        if (getDistance(y, x, nodes[i][0], nodes[i][1]) < distance) 
        {
            return false;
        }
    }
 
    return true;
}
 
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> timetable) {
    int answer = 0;
 
    sort(timetable.begin(), timetable.end());
 
    int maxPeople = 0, people = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
 
    for (int i = 0; i < timetable.size(); i++) 
    {
        while (!pq.empty() && pq.top() < timetable[i][0]) 
        { 
            pq.pop(); 
            people--; 
        }
 
        pq.push(timetable[i][1]);
        people++;
 
        maxPeople = max(maxPeople, people);
    }
 
    if (maxPeople == 1) return 0;
 
    for (int distance = n * 2 - 2; distance >= 1; --distance) // 각각 거리마다 전부 다 배치해보기.
    {
        for (int standY = 0; standY < n; ++standY)
        {
            for (int standX = 0; standX < n; ++standX)
            {
                vector<vector<int>> curNodes;
                curNodes.push_back({ standY,standX });
 
                
                for (int y = standY; y < n; ++y)
                {
                    for (int x = 0; x < n; ++x)
                    {
                        if (canPlace(y, x, curNodes, distance))
                        {
                            curNodes.push_back({ y,x });
                        }
                    }
                }
 
                if (curNodes.size() == maxPeople)
                {
                    return distance;
                }
            }
        }
    }
 
    return answer;
}

 

나는 생각치도 못한 방법으로 풀어야 했던 문제. 

이 문제에서는 일단 회원이 가장 겹치는 구간을 찾아야하는게 첫번째 과제다.

제일 쉽고 무식(?)하게 푸는 방법으로는 그냥 시간범위만큼의 배열을 선언하고 각 값을 다 카운팅한다음, 값이 가장 높은 구간의 길이를 구하면 된다.

 

이번문제같은경우는 인풋값이 작아서 이걸로도 상관없긴 한데, 만약 값이 클 경우를 대비해 다른 방법을 찾아봤다.

우선순위큐를 사용하면 좀 더 효율적으로 찾을 수 있게 되는데, 일단 timetable을 시작시간 기준으로 정렬해준 다음, 조건에 따라 pop을 해주고 무조건 끝나는시간을 push해준다.

pop하는 조건으로는 우선순위큐의 top의 값, 즉 우선순위큐에 들어있는 도착시간들 중 가장 작은값이, 현재 선택한 회원의 시작시간값보다 작을 경우 pop해주는 것이다. 끝나는시간이 시작시간보다 작으니, 겹치지가 않기때문에 빼버리는것이다.

이 부분도 직접 노트에다가 대충 끄적여서 비교해보면 바로 이해가 갈것이다.

 

이렇게 최대겹치는 수를 구한다면 그다음이 또 문제다.

결론만 말하자면, 각 거리마다 최대로 배치할 수 있는만큼 배치를 다 해본다. 그다음 다 배치를 했을때 인원수가 우리가 구한 최대겹치는수랑 일치한다면, 그때의 거리값이 바로 정답이다.

 

로직에서 첫 for문의 변수가 distance인게 보일것이다. 각 거리값을 기준으로 전부 다 배치를 해보겠다는 것이다.

distance가 4라면, 인원을 락커룸에다가 최소 4이상의 거리가되도록 전부 배치해보는것이다.

그렇게 배치한인원이 3명이고, 우리가 구한 값(최대 겹치는 값)과 동일하면 그떄의 distance인 4가 정답인 것이다.

 

문제를 잘 해석한다면 이게 왜 정답인지 이해가 간다.

문제에선 그저 '헬스장을 이용한 손님들 중 가장 가까웠던 거리'를 구하라고 할 뿐이다.

이때 가까워지는 경우는 손님수가 많을 때이다. 손님이 많아지면 어쩔 수 없이 가깝게 배치할 수 밖에 없는것이다.

 

그래서 아예 역으로 각 거리마다 되는대로 완전탐색하면서 최대로 배치해버리고 비교하는 것이다.