1946번 - 신입 사원(c++)

🗒 1946번 문제

📌 재정렬한 순서대로 최대 인원수를 찾자(회의실배정과 유사) ❗️

🧑🏻‍💻 회의실배정 보러가기

1️⃣ 받아온 서류 성적과 면접 성적을 Vector를 통해서 받는다.

2️⃣ sort함수를 통해서 vector를 정렬
-> queue의 경우에는 begin(), end()를 사용할 수 없기에 vector를 사용하면 정렬이 좀 더 편리

3️⃣ vector로 받아온 순서를 queue에 넣고 최대 인원수를 찾는다

4️⃣ 현재 사람의 서류 성적과 현재 사람의 면접 성적이 모두 이전 사람들보다 떨어지면 pop시키기
-> 이전 사람들보다 떨어진다는 건 이전 사람들의 최고 성적보다 순위가 낮다는 것
-> 이전 최고 성적이 1인데, 나의 순위는 3인 것

5️⃣ (1, 2) (2, 1) (3, 4), (5, 2) 라고 할 때, 
-> 지원자 (5, 2)에 갔을 때는 최고 성적이 (1, 1)이다

6️⃣ 최고 성적이 갱신될 수 있도록 if문을 통해서 계속 first, second값을 바꿔준다.
-> first가 현재까지 최고 성적이라고 해서 second까지 최고 성적 아니기에 if문을 통해서 걸러주기

➰ 코드로 나타낸 1946번 ➰

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int testcase, num, cnt;
vector<pair<int, int>> recruiter;
queue<pair<int, int>> q;

void recruiting() {
    for (int i = 0; i < num; i++) {
        int doc, interview;
        cin >> doc >> interview;
        recruiter.push_back(make_pair(doc, interview));
    }
    
    sort(recruiter.begin(), recruiter.end());
    
    for (int i = 0; i < num; i++) {
        q.push(make_pair(recruiter[i].first, recruiter[i].second));
    }
    
    // 첫 지원자의 성적 넣기
    int first = q.front().first;
    int second = q.front().second;
    while (!q.empty()) {
    	// 해당 지원자의 성적이 현재까지 지원한 사람들의 점수보다 좋다면 갱신하기 
        // first의 점수만 더 좋았다면 first만 바뀔 것이고, second만 좋았다면 second만 바뀔 것임
        if (first > q.front().first) first = q.front().first;
        if (second > q.front().second) second = q.front().second;
        q.pop();
        cnt++;
        if (q.empty()) break;
        // first, second보다 크다는 것은 first, second보다 성적이 안좋다는 것 -> pop!
        while (first < q.front().first && second < q.front().second) {
            q.pop();
            if (q.empty()) break;
        }
    }
    
    cout << cnt << endl;
}

int main() {
    cin >> testcase;
    
    while(testcase--) {
        cnt = 0;
        cin >> num;
        recruiting();
        // vector 안의 값을 제거해주기 -> queue는 empty되어서 없어졌기에 따로 초기화 X
        recruiter.clear();
    }
}