[BOJ/백준] 1931 (회의실 배정) C++
주제
그리디
아이디어
- 종료시간 기준으로 오름차순 배열
- 가장 먼저 끝나는 회의 기준, 겹치는 회의 다 삭제하기!
소스코드
시간초과
/*
boj1931.cpp
2021-01-08 정설희
회의실 배정
*/
#include <bits/stdc++.h>
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
return a.second < b.second;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector <pair<int, int>> vec;
int n; cin >> n;
for (int i = 0; i < n; i++) {
int t1, t2; cin >> t1 >> t2;
vec.push_back({ t1,t2 });
}
sort(vec.begin(), vec.end(),cmp);
int cnt = 0;
while (vec.size()) {
cnt++;
int idx = 0;
int sz = vec.size();
vector <pair<int, int>> tmpV;
for (int i = 1; i < sz; i++) {
if (vec[i].first >= vec[idx].second)
tmpV.push_back(vec[i]);
}
vec = tmpV;
}
cout << cnt;
}
시간초과가 뜬다..
성공!
/*
boj1931.cpp
2021-01-08 정설희
회의실 배정
*/
#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int, int>a, pair<int, int>b) {
if (a.second == b.second) {
return a.first < b.first;
}
else {
return a.second < b.second;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector <pair<int, int>> vec;
int n; cin >> n;
for (int i = 0; i < n; i++) {
int t1, t2; cin >> t1 >> t2;
vec.push_back({ t1,t2 });
}
sort(vec.begin(), vec.end(),cmp);
int cnt = 1;
int now = vec[0].second;
for (int i = 1; i < n; i++) {
if (vec[i].first >= now) {
cnt++;
now = vec[i].second;
}
}
cout << cnt;
}
훨씬 간단하다.. for문 한번만 돌면서 그 때 그 때 now를 바꿔준다!
배운점
vector 요소 삭제 : vec.erase(vec.begin()+i);
vec.erase(vec.begin()+i);
이렇게 하면 vec[i]를 삭제 할 수 있다. 그 뒤부터 index가 하나 씩 당겨진다.
for문 조건 속 변수 변하지 않게 조심!
이게 무슨말이냐 하면..
for (int i = 1; i < vec.size(); i++) {
if (vec[i].first < vec[idx].second)
vec.erase(vec.begin() + i);
}
위와 같은 경우에, vec의 요소가 하나씩 줄어들면서 vector의 사이즈가 바뀐다 -> ERROR
그걸 방지하기 위해서
int sz = vec.size();
for (int i = 1; i < sz; i++) {
if (vec[i].first < vec[idx].second)
vec.erase(vec.begin() + i);
}
이렇게 sz로 바꿔줬는데도, ERROR가 떴다.
그 이유는 vector의 요소들이 erase 되면서 더이상 vec[i] 가 vec[i]가 아니게된것..!
지워질 때 마다 그 뒤부터 idx 하나 씩 땡겨진다
Author And Source
이 문제에 관하여([BOJ/백준] 1931 (회의실 배정) C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@xxeol/BOJ백준-1931-회의실-배정-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)