[백준] 1931 회의실 배정 [C++]

Seongho·2021년 12월 31일

C++ STL 그리디알고리즘 백준알고리즘

백준

목록 보기

2/23

그리디 알고리즘

이 문제는 그리디 알고리즘으로 풀 수 있다. 가능한 많은 회의를 겹치지 않게 배정하는 문제로, 그리디 알고리즘의 Interval Scheduling Problem에 해당한다.

해결방법

회의의 끝나는 시간이 빠른 순서로 정렬한 후, 정렬된 순서대로 겹치지 않는 회의들을 골라 배정한다. 이 문제에서는 최대 몇개의 회의가 배정될 수 있는지 물었으므로, 회의의 수를 count하면 된다.

sort [C++ / STL]

배열을 정렬하는 라이브러리로, <algorithm> 헤더파일에 포함되어 있다.
template <typename T>				//함수 원형
void sort(T start, T end, Compare comp);
마지막 인자를 넣지 않으면 start부터 end 이전까지의 값이 디폴트 값으로 오름차순 정렬된다. 세번째 인자는 사용자가 정의한 함수를 기준으로 정렬을 수행한다. 특정 값을 기준으로 정렬할 수 있다.
sort(arr, arr+n);				//arr의 인덱스 0부터 n-1까지 정렬
sort(v.begin(), v.end());			
sort(v.begin(), v.end(), compare);              //사용자 정의 함수 사용
sort(v.begin(), v.end(), greater<자료형>());     //내림차순 
sort(v.begin(), v.end(), less<자료형>());        //오름차순 (default)
**vector에서 start()는 벡터의 시작주소, end()는 마지막 데이터 다음 주소를 리턴한다.

전체코드(내 코드)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//끝나는 시간이 빠른 것 순서대로 배정

class Meet {
public:
	int start;
	int end;
	Meet() {
		start = 0;
		end = 0;
	}
	Meet(int start, int end) {
		this->start = start;
		this->end = end;
	}
};
bool cmp(const Meet& meet1, const Meet& meet2) {
	if (meet1.end == meet2.end) {
		return meet1.start < meet2.start;	//같을 경우 시작시간 기준으로 오름차순 정렬
	}
	else {
		return meet1.end < meet2.end;		//end를 기준으로 오름차순 정렬
	}
}

int main() {
	ios_base::sync_with_stdio(false);		//stdio 버퍼 동기화 해제
	int meeting = 0, end = 0;				//회의 수, 끝나는시간
	cin >> meeting;
	vector<Meet> meet;						//회의 저장할 벡터
	for (int i = 0; i < meeting; i++) {
		//근데 이거 왜 protedted로 하면 접근 안되는지??
		int start = 0, end = 0;
		cin >> start >> end;				//회의의 시작시간, 끝나는 시간 입력
		Meet m(start, end);					//회의 객체 생성
		meet.push_back(m);					//벡터에 추가
	}
	sort(meet.begin(), meet.end(), cmp);		//끝나는 시간이 빠른 순서대로 정렬 

	int cnt = 1, idx = 1;
	end = meet[0].end;					//배정된 회의의 끝나는 시간.
	while (idx < meeting) {
		if (end <= meet[idx].start) {	//배정된 회의의 끝나는 시간이 현재 순회중인 인덱스의 시작하는 시간보다 작거나 같으면 현재 회의 배정
			end = meet[idx].end;
			cnt++;
		}
		idx++;
	}
	cout << cnt;		//최종 배정된 회의 수 출력

	return 0;
}

다른사람 코드

vector<pair<type, type>>		//선언
make_pair(value, value)			//값 할당 
두 인자를 first(첫번째 인자 값), second(두번째 인자 값)로 접근할 수 있다. 연관된 두개의 값에서 각각의 조건에 따라 값을 정렬할 때 주로 사용한다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int main()
{
	int N, end, begin;

	vector<pair<int, int>> schedule;

	cin >> N ;

	for (int i = 0; i < N; i++)
	{
		cin >> begin >> end;
		schedule.push_back(make_pair(end, begin));
	}
	
	sort(schedule.begin(), schedule.end());
	
	int time = schedule[0].first;
	int count = 1;
	for (int i = 1 ;i < N; i++) 
	{
		if (time <= schedule[i].second )
		{
			count++;
			time = schedule[i].first;
		}
	}

	cout << count;
}