BOJ
BOJ::12764 싸지방에 간 준하
BOJ Gold 5
BOJ::12764 싸지방에 간 준하
[BOJ] : https://www.acmicpc.net/problem/12764
- Level : Gold 5
시사점
- priority_queue와 set을 자연스럽게 다룰 수 있으면 풀 수 있는 문제라고 생각합니다.
- 쉽게 답을 도출해내지 못하였고, 이번 기회를 통해 set을 활용할 수 있었습니다.
STL :: set insert, erase, begin, end 등의 함수를 제공합니다. set의 특성으로는 logN만에 삽입과 삭제가 가능합니다. 또한, set은 항상 정렬된 상태를 유지합니다.
이해(5)
- 사람들이 컴퓨터를 이용하고자 하는 시작시간과 종료시간이 주어집니다.
- 가용 가능한 컴퓨터의 갯수를 늘려가면서, 최소한의 컴퓨터로 전체 인원을 수용하고자 합니다.
- 이때, 최소 가용 컴퓨터 갯수와, 각 컴퓨터 자리마다 사용한 사람의 수를 출력합니다.
설계(30)
int seat; // 사용한 전체 컴퓨터의 수 입니다.
int eachSeat[MAX_N]; // 각 좌석에 앉은 횟수입니다.
priority_queue<pair<int,int> > pq; // 종료시간(low), 사용중인 PC번호
set<int> leftPC; // 전체 seat개의 컴퓨터 중 사용되지 않는 컴퓨터의 목록을 정렬된 상태로 유지합니다.
pair<int,int> time[MAX_N]; // 시작시간, 종료시간을 담습니다.
- 로지컬하게 아래의 순서를 따릅니다.
- leftPC는 사용중이지 않은 PC의 목록을 유지합니다.
- pq는 사용중인 컴퓨터에 대한 목록을 유지합니다.
- 전체 n개의 input에 대해
- pq를 확인하며, pop할 수 있는 만큼 pop합니다.
- 즉, 사용시간이 종료된 PC들을 pop하고 해당 PC는 가용가능해지므로 leftPC에 넣습니다.
- leftPC에 남는 자리가 있는 경우 현재 index에 해당하는 사람이 차지한 후, pq에 넣습니다.
- 남는 자리가 없는 경우 전체 PC의 수를 한자리 늘려서 차지한 후, pq에 넣습니다.
- pq를 확인하며, pop할 수 있는 만큼 pop합니다.
시간 복잡도
공간 복잡도
구현(x)
#include<iostream>
#include<queue>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int MAX_N = 100000 + 1;
int n;
int seat; // 전체 좌석 수 입니다.
int eachSeat[MAX_N]; // 각 좌석에 앉은 횟수입니다.
priority_queue<pair<int, int> > pq; // 종료시간(low), 사용중인 PC번호 // 현재 PC를 사용중인 목록을 유지합니다.
set<int> leftPC; // 전체 seat개의 컴퓨터 중 사용되지 않는 컴퓨터의 현황을 유지합니다.
pair<int, int> time[MAX_N];
void solve(){
for (int i = 0; i < n; i++){
// 사용 종료된 PC의 좌석들을 반납합니다.
while (!pq.empty()){
if ((-pq.top().first) <= time[i].first){
leftPC.insert(pq.top().second);
pq.pop();
}
else
break;
}
// 남은 자리가 없는 경우
if (leftPC.empty()){
pq.push({ -time[i].second, seat });
eachSeat[seat]++;
seat++;
}
// 남은 자리가 있는 경우
else{
auto seatIdx = leftPC.begin();
pq.push({ -time[i].second, *seatIdx });
eachSeat[*seatIdx]++;
leftPC.erase(seatIdx);
}
}
cout << seat << endl;
}
int main(){
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 0; i < n; i++){
cin >> time[i].first >> time[i].second;
}
sort(time, time + n);
solve();
for (int i = 0; i < seat; i++)
cout << eachSeat[i] << " ";
cout << endl;
return 0;
}