[백준] 1931. 회의실 배정 (+ STL vector)

문제 

https://www.acmicpc.net/problem/1931



풀이

그리디 알고리즘으로 풀 수 있는 문제이다. 아래와 같은 과정을 통해서 풀 수 있다.

• 벡터에 시작하는 시간과 끝나는 시간을 한쌍으로 저장해준다.
• 끝나는 시간이 가장 작은 순으로 정렬해준다.
• 정렬한 것을 기준으로 끝나는 시간이 같으면 시작하는 시간이 작은 순으로 정렬해준다. 
• 끝나는 시간이 가장 작은 것을 선택하면서 다음 pair의 시작하는 시간이 이전 pair의 끝나는 시간보다 크거나 같은 것을 선택해준다. (시간이 겹치면 안되므로)
• 이 과정을 반복해준다.

소스코드

//
//  MeetingRoomAssignment.cpp
//  test
//
//  Created by 신기열 on 24/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

bool compare(const pair<int, int>& a, const pair<int, int>& b){
    
    if(a.second == b.second){
        return a.first < b.first;
    }
    else return a.second < b.second;
}

int main(){
    
    int n, total = 1, curr;
    cin >> n;
    vector<pair<int, int> > v;
    v.resize(n);
    
    for(int i = 0; i < n; i++){
        int p, q;
        cin >> p >> q;
        v[i].first = p; v[i].second = q;
    }
    
   // vector > :: iterator it;
    
    sort(v.begin(), v.end(), compare);

//    for(it = v.begin(); it != v.end(); it++){
//        cout << it -> first << " " << it -> second << '\n';
//    }
    
    curr = v[0].second;
    for(int i = 1; i < n; i++){
        
        if(v[i].first >= curr){
            curr = v[i].second;
            total++;
        }
    }

    cout << total;
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Greedy/MeetingRoomAssignment.cpp




++
벡터의 정렬에 대해선 이전에 다뤘던 적이 있다만 이번에 얘기할 것은 vector<pair<int, int> >의 정렬과 sort함수에서 직접 만든 compare함수를 적용하는 방법에 대해서이다.
일단 위의 소스코드에서 확인할 수 있는 것처럼 비교함수는 bool 함수를 이용하여 pair : a, b에 관해 정렬하는 조건을 return 해주는 형태로 만들 수 있다.

bool compare(const pair<int, int>& a, const pair<int, int>& b){
    
    if(a.second == b.second){
        return a.first < b.first;
    }
    else return a.second < b.second;
}

이 때 const는 변수를 상수화 하는 것이다. const는 값을 변경할 수 없으며, 메모리 위치도 바꿀 수 없고, 상수화 시키기 때문에 사용할 때마다 사본을 만들어 사용하는 것이 아닌 사본이 하나만 생기기 때문에 메모리 절약에 도움이 된다.
참고로 #define은 전처리 과정, 즉 컴파일 전에 미리 처리해버리는 것이며 사용할 때마다 사본이 생기게 된다.



비교함수를 만들었으면 이제 정렬하는 것은 매우 간단하다. 기존의 sort에서 뒤에 비교함수를 선언해주기만 하면 된다. 즉 vector v의 처음부터 끝까지 돌면서 compare의 원칙에 따라 정렬해주기만 하면 된다.

sort(v.begin(), v.end(), compare);