[Queue/Deque] 큐/덱 - 미팅 주선 프로그램

미팅 주선 프로그램

간단한 미팅 주선 프로그램을 만들고자 한다. 덱 (deque)을 이용하여 남성 큐와 여성 큐를 구현한다 (여기서 덱은 배열을 이용해서 구현해야한다). 매 시간 한명의 고객이 미팅 주선을 요청하기 위해 방문하면 성별에 맞추어 큐의 맨 뒤에 삽입한다. 만약에 해당 고객이 돈을 더 내서라도 순서를 기다리지 않고 즉시 미팅이 주선되길 원하면 큐의 맨 처음에 삽입한다.

매 시간 고객이 대기열에 입장하고 나면, 남성 큐와 여성 큐에서 맨 앞에 있는 남성과 여성의 미팅이 매칭된다. 만약 매칭할 남성 또는 여성이 없는 경우 다음 시간으로 넘어간다.

Input

입력의 첫 줄에는 미팅 주선소에 입장하고자 하는 총 인원의 수 n (1 <= n <= 100)이 들어온다.

그 다음 줄부터는 (시간, 이름, 성별, 입력 위치)가 들어오며 각 줄은 공백으로 구분된다.

성별은 m은 남성, f는 여성을 의미하고, 입력 위치는 F는 front, R은 rear를 의미한다.

이름은 최대 30자를 넘지 않는다.

Output

커플이 매칭되는 즉시 매칭된 사람의 이름을 공백으로 구분하여 남성, 여성 순으로 출력한다. 이때 출력 형식은 다음과 같다

• Matched : name1 name2

모든 입력이 종료될 경우, (매칭된 커플의 수, 대기열에 남아 있는 남성의 수, 대기열에 남아 있는 여성의 수)를 공백으로 구분하여 출력한다.

Sample Input 1

5

1 Kim m R

2 Na m R

3 Park m F

4 Lee f F

5 Choi f F

Sample Output 1

Matched : Park Lee

Matched : Kim Choi

2 1 0

 

정답 : 

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main(){
    int n; //미팅에 입장하고자 하는 총 인원수
    cin >> n;

    // string s;
    int id;
    string name;
    char sex, type;
    deque<string> fe;   //여자 덱
    deque<string> ma;   //남자 덱
    int ans=0; //매치된 미팅 수

    //덱에 차곡차곡 넣어주기
    for(int i=0; i<n; i++){
        string him, her;
        cin >> id;
        cin >> name;
        cin >> sex;
        cin >> type;
        if(sex=='f'&&type=='F'){
            fe.push_front(name);
        }
        else if(sex=='f'&&type=='R'){
            fe.push_back(name);
        }
        else if(sex=='m'&&type=='F'){
            ma.push_front(name);
        }
        else if(sex=='m'&&type=='R'){
            ma.push_back(name);
        }

        if(!ma.empty() && !fe.empty()){ //여자큐, 남자큐 모두 비지 않았으면
            him = ma.front();
            ma.pop_front(); //남자큐 맨앞분 빼고
            her = fe.front();
            fe.pop_front(); //여자큐 맨앞분 빼고
            ans++;  //현재 매치된 미팅 수 ++
            cout << "Matched : "<<him<<" "<<her<<endl; 
        }
        
    }

    //반복문을 돌고 각 성별 큐에 남은 사람들 수 세기
    int men=0;
    int women=0;
    while(!ma.empty()){
        ma.pop_front();
        men++;
    }
    while(!fe.empty()){
        fe.pop_front();
        women++;
    }

    //매치된 커플 수랑 남은 남자, 남은 여자 수 출력하기
    cout << ans <<" "<< men <<" "<< women << endl;

    return 0;
}