[BOJ / 그리디] 1931번 회의실 배정 C++ 풀이(+sort/pair사용법)

백준 1931번은 그리디 알고리즘을 이용해서 푸는 문제입니다. 이 문제를 풀면서 vector와 sort, pair를 처음 써봤는데 신기했습니다. 맨 아래 참고용으로 sort와 pair 사용법을 간단하게 정리해 두었습니다.

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

1931번: 회의실 배정

---

문제 조건은 정리하면 (1) 회의의 시작시간과 끝 시간의 차이가 적고 한 회의의 끝시간과 다른 회의의 (2) 시작시간의 차이가 최대한 작게 나도록 하는 것입니다. 이 문제를 풀기위한 핵심 알고리즘은 아래와 같습니다.

• vector의 pair로 입력 받기
• 두 번째 인자를 기준으로 정렬하기

먼저 파이썬의 튜플과 비슷한 vector의 pair로 쌍을 입력받습니다.
다음으로는 두 번째 인자를 기준으로 정렬하는 것입니다. 첫 번째 인자를 기준으로 정렬하면 (2) 조건은 만족시키지만 (1) 번은 만족 못 시키는데 두 번째 인자를 기준으로 하면 두 조건 모두 만족시켜서 두 번째 인자를 기준으로 쌍을 정렬했습니다.

여기까지 정렬한 결과는 아래와 같습니다. 그런데 두 번째 인자를 기준으로 정렬하려면 입력받을 때 p.second, p.first순으로 입력받으면 됩니다.

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N,connect,cnt;
 
 
int main() {
    // 반복횟수 입력 받기
    cin >> N;
 
    // 시간 쌍 입력 받는 pair선언
    vector<pair<int, int>> p(N);
 
    // pair 입력 받기
    for (int i = 0; i < N; i++)
    {
        // pair를 sort하면 첫 번째 인자를 오름차순 정렬해서 두 번째 값을 정렬하기 위해 second와 first순서를 바꿔 입력 받음
        cin >> p[i].second >> p[i].first;
    }
 
    // 끝나는시간을 오름차순으로 정렬
    sort(p.begin(), p.end());
 
 
    cout << endl;
    
    // 정렬한 회의 시작시간과 끝시간은 각각 second와 first에 저장되어 
    cout<<"[second / first]"<<'\n';
    for (int i = 0; i < N; i++)
    {
        // pair를 sort하면 첫 번째 인자를 오름차순 정렬해서 두 번째 값을 정렬하기 위해 second와 first순서를 바꿔 입력 받음
        cout<<p[i].second <<' '<< p[i].first<<'\n';
    }
}

출력 결과

위 정렬 결과를 기반으로 아래와 같은 구조의 for문으로 답을 구할 수 있다.

 

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N,connect,cnt;
 
 
int main() {
    // 반복횟수 입력 받기
    cin >> N;
 
    // 시간 쌍 입력 받는 pair선언
    vector<pair<int, int>> p(N);
 
    // pair 입력 받기
    for (int i = 0; i < N; i++)
    {
        // pair를 sort하면 첫 번째 인자를 오름차순 정렬해서 두 번째 값을 정렬하기 위해 second와 first순서를 바꿔 입력 받음
        cin >> p[i].second >> p[i].first;
    }
 
    // 끝나는시간을 오름차순으로 정렬
    sort(p.begin(), p.end());
 
 
    cout << endl;
 
    // 첫 번째 수가 connect(0으로 시작)q보다 크면 해당 케이스의 second를 connect에 담아서 갱신
    for (int i = 0; i < N; i++) {
        if (p[i].second >= connect) {
            connect = p[i].first;
            cnt++;
        }
    }
}

 

\\

 

 

---

+ sort와 pair사용법

개인적으로 vector와 STL 등의 C++ 라이브러리를 잘 모르는데 이번 기회에 조금 배웠습니다.

• pair 선언 법 (크기 생략 가능)

vector <pair <자료형, 자료형> 변수명(크기)

• pair 입력받기 ([i] 생략 가능)

cin>>p([i]). first>>p([i]). second;

• pair의 first 기준으로 정렬

참고로 디폴트가 첫 번째 인자를 기준으로 정렬이고 cmp함수 추가 시 두 번째 인자 기준 가능

sort(페어 변수명. begin(), 페어 변수명. end());

++ 참고 vector랑 stl 차이
// STL은 Standard Template Library로 로 표준 템플릿 라이브러리를 말한다.
// STL - container(임의 타입 객체 보관), iterator(컨테이너 원소에 접근하는 반복자), algorithm(반복자로 작업 수행)
// stl에 컨테이너에는 시퀀스 컨테이너(vector,list,deque)와 연관 컨테이너가 있다.