[프로그래머스] 몸짱 트레이너 라이언의 고민 / c++

몸짱 트레이너 라이언의 고민

헬스장에서 일하는 몸짱 트레이너 라이언은 최근 손님들에게 불평을 많이 들었다.
그것은 옷을 갈아입는데 다른 사람과 너무 가까워서 옷을 갈아입기가 불편하다는 것이었다.

불만을 해결하기 위해 고민하던 라이언은 손님들의 예약시간을 참고해서 되도록이면 서로 멀리 떨어지도록 키를 나눠주기로 마음먹었다. 예를 들어, 락커들이 3x3 정사각형 모양으로 배치되어있고, 동시간대에 2명의 손님이 예약되어있다면 아래와 같이 락커를 할당하는 것을 고려해볼 수 있다.

라이언이 일하는 헬스장은 아래와 같은 상황이라고 가정하자.

• 락커는 정사각형으로 배치되어있고, 락커 사이에 옷을 갈아입을 공간이 있다. 단, 이 공간은 계산에서 제외된다.
• 락커 간 거리는 상하좌우는 1로, 대각선은 2로 계산한다.
• 손님들은 철저하게 예약시간에 맞춰 락커를 이용하고, 퇴실하는 시간까지 락커를 차지한다.
• 영업시간은 오전 10시부터 오후 10시까지이다.
• 헬스장은 예약제로 운영되므로 락커의 개수보다 더 많은 손님들이 동시간대에 몰리는 경우는 없다.

이런 조건에서 헬스장을 이용한 손님들 중 가장 가까웠던 손님 간의 거리는 얼마일까?

 

입력 형식

입력은 정사각형 한 변의 길이 n과 손님수 m, 그리고 각 손님의 예약된 입실/퇴실 시간 timetable로 주어진다. 제한조건은 다음과 같다.

• 0 < n <= 10
• 0 <= m <= 1,000
• timetable은 m × 2 크기의 2차원 배열이다. 각 행은 손님의 입실시각과 퇴실시각이 분 단위로 환산된 값 (t1, t2)가 들어있다.
  • t1, t2에 대해서는 다음 조건이 성립한다. 600 <= t1 < t2 <= 1,320

 

출력 형식

할당된 락커들 간 거리 중 최소거리를 리턴한다. 손님 간에 이용 시간이 한 번도 겹치지 않을 경우에는 0을 리턴한다.

n	m	table	answer
3	2	[[1170,1210], [1200,1260]]	4
2	1	[[840,900]]	0
2	2	[[600,630],[630,700]]	2
4	5	[[1140,1200],[1150,1200],[1100,1200],[1210,1300],[1220,1280]]	4

 

 

 

접근법

---

1. 헬스장의 예약 내역이 주어졌을때, 구현을 통해서 구하는 것이 아닌, 회원수가 최대인 구간만 구하게 되면, 나머지는 회원수가 최대인 시간의 배열의 부분 집합으로 구할 수 있습니다.
2. priority_queue 를 사용하여, 그리디하게 회원수가 최대인 시간을 구해주었으며,
3. 문제의 핵심인 락커의 위치를 구할때는 락커의 각 부분배열을 완전탐색으로 구해주어, 시간 내에 문제를 해결할 수 있었습니다.

 

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

using namespace std;

const int MAX = 1320 + 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;
    
    // 한명밖에 존재하지 않는다면, 0 을 return
    int maxCrowded = getMaxUser(timetable);
    if(maxCrowded == 1) return 0;
    
    for(int distance = 2 * n - 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;
}