BOJ 11666) 워크스테이션 배정

시간 제한 - 10s

메모리 제한 - 256MB

 

---

풀이

기본적인 개념은 잠금해제를 하지 않고 사용할 수 있는 컴퓨터를 pool로 관리한다는 개념에서 시작

컴퓨터의 사용 종료와 종료 후 락이 걸리는 시간을 오름차순으로 관리한다. 이미 락이 걸린 컴퓨터는 항상 다시 잠금을 해제해야하기 때문에 연구원의 입실 시간을 기준으로 이미 락이 걸린 컴퓨터는 전부 관리 목록에서 제거해준다.

만약 종료가 된 이후의 컴퓨터이고 연구원의 시작시간이 락이 걸리기 전이라면 해당 컴퓨터는 잠금을 다시 해제하지 않고 절약할 수 있다.

 

입력

연구원의 수 n과 사용 종료 후 잠금이 걸리는 시간까지의 길이 m이 입력되고 연구원의 입실과 입실 이후 사용 시간이 n회 입력된다.

 

자료구조

연구원의 입장 시간과 사용 시간을 입력받을 <int, int>형 배열

먼저 사용이 완료된 컴퓨터를 우선 순서로 두는 int 형 우선 순위 큐

 

로직

1. 연구원의 입장과 사용을 입장 시간을 기준으로 정렬해 먼저 입장한 사람이 잠금이 얼마 남지않은(유통기한) 워크 스테이션을 사용
2. 입장 시간을 기준으로 pool에 있는 워크스테이션 중 잠궈지는 시간(종료 시간 + m)이 입장 시간 이전이라면 사용이 끝났으나 시간이 지나 잠금이 되어버린 객체이므로 pop을 통해 관리 대상에서 제외
3. 남아있는 관리 대상의 잠금 시간(종료 시간 + m)이 연구원의 입장 시간보다 이후라면 해당 워크 스테이션은 사용이 끝났으나 잠금 해제 없이 사용할 수 있으므로 절약한 것 (해당 PC의 종료시간을 현재 입장하는 연구원의 종료시간으로 수정)
4. 남아있는 관리 대상의 종료 시간이 연구원의 입장시간보다 이후라면 해당 대상은 아직 사용중인 것으로 간주해 연구원을 입장시키고 pool에 새롭게 추가

---

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int n, m;

	cin >> n >> m;
	vector<pair<int, int>> users(n);
	priority_queue<int, vector<int>, greater<int>> pq;
	
	for (int i = 0; i < n; i++) cin >> users[i].first >> users[i].second;
	
	sort(users.begin(), users.end());	//	입력 오름차순 정렬
	
	int ret = 0;
	for (auto user : users) {
		//	이미 잠긴 워크스테이션은 관리 대상에서 제거
		while (!pq.empty() && pq.top() + m < user.first) pq.pop();

		if (!pq.empty() && pq.top() <= user.first) {	// 잠금 X
			pq.pop();//	오래된 스테이션의 종료 시간을 아래에서 교체해줌
			ret++;   //	절약한 것으로 간주
		}
		pq.push(user.first + user.second);	//	새로운 관리 대상 추가
	}
	cout << ret << endl;	//	절약한 횟수 출력
	return 0;
}

 

시간 복잡도

입력 값 정렬에 필요한 시간과 우선순위 pool 이용에 O(N log N)의 시간복잡도가 필요한데 문제의 시간제한이 10s이다; 오타인듯