본문 바로가기

백준/C++

[Baekjoon/C++] 20006번 - 랭킹전 대기열

[백준] Baekjoon Online Judge

문제로 이동

 

문제

종운이는 운영하던 게임에 랭킹전 기능을 추가하려고 한다. 플레이어 간의 실력차이가 있을 수 있기 때문에 입장을 신청하면 자신과 비슷한 레벨의 플레이어들을 매칭하여 게임을 시작하게 하려고 한다.

플레이어 간 매칭을 해주는 시스템은 다음과 같다.

  1. 플레이어가 입장을 신청하였을 때 매칭이 가능한 방이 없다면 새로운 방을 생성하고 입장시킨다. 이떄 해당 방에는 처음 입장한 플레이어의 레벨을 기준으로 -10부터 +10까지 입장 가능하다.
  2. 입장 가능한 방이 있다면 입장시킨 후 방의 정원이 모두 찰 때까지 대기시킨다.
    1. 이때 입장이 가능한 방이 여러 개라면 먼저 생성된 방에 입장한다.
  3. 방의 정원이 모두 차면 게임을 시작시킨다.

플레이어의 수 p, 플레이어의 닉네임 n, 플레이어의 레벨 l, 방 한개의 정원 m이 주어졌을 때 위와 같은 방법으로 매칭해주고 최종적으로 만들어진 방의 상태와 입장 플레이어들을 출력하는 프로그램을 작성하자.

 

입력

첫 번째 줄에는 플레이어의 수 p(1 ≤ p ≤ 300)와 방의 정원 m(1 ≤ m ≤ 300)가 주어진다.

두 번째 줄부터 p개의 줄에는 플레이어의 레벨 l (1 ≤ l ≤ 500)과 닉네임 n이 공백을 두고 주어진다.

입력된 순서대로 게임을 시작한다.

닉네임은 중복되지 않으며 공백을 포함하지 않는 알파벳 소문자로 되어있으며 닉네임의 길이는 16을 넘지 않는다.

 

출력

모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백으로 구분된다.

방은 생성된 순서대로 출력한다.

방에 있는 플레이어들의 정보는 닉네임이 사전순으로 앞서는 플레이어부터 출력한다.

방이 시작되었으면 Started!를 대기 중이면 Waiting!을 출력시킨다.

 


풀이

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

struct Player {
    int level = 0;
    string name;
};

int p, m;
vector<Player> room[301];

bool compare(Player a, Player b);

bool compare(Player a, Player b) {
    return a.name < b.name;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> p >> m;

    while (p--) {
        int l;
        string n;

        cin >> l >> n;

        for (int i = 0; i < 301; i++) {
            // 이미 정원이 찬 방인 경우
            if (room[i].size() == m) continue;

            // 새로운 방을 만들어야 하거나 방 매칭 성공 시
            if (room[i].size() == 0 || (room[i][0].level - 10 <= l && l <= room[i][0].level + 10)) {
                room[i].push_back({ l, n });
                break;
            }
        }
    }

    for (int i = 0; i < 301; i++) {
        // 텅 빈 방은 아직 생성되지 않은 방과 같기에
        if (room[i].size() == 0) break;

        sort(room[i].begin(), room[i].end(), compare);

        // 출력
        if (room[i].size() == m) cout << "Started!\n";
        else cout << "Waiting!\n";

        for (Player player : room[i]) 
            cout << player.level << ' ' << player.name << '\n';
    }

    return 0;
}

 

    while (p--) {
        int l;
        string n;

        cin >> l >> n;

        for (int i = 0; i < 301; i++) {
            // 이미 정원이 찬 방인 경우
            if (room[i].size() == m) continue;

            // 새로운 방을 만들어야 하거나 방 매칭 성공 시
            if (room[i].size() == 0 || (room[i][0].level - 10 <= l && l <= room[i][0].level + 10)) {
                room[i].push_back({ l, n });
                break;
            }
        }
    }

 입력 받은 플레이어에게 방을 매칭해주는 부분의 코드이다. 가장 첫번째 방부터 탐색하는데, 텅빈 방을 만나거나 조건에 맞는 방을 발견하면 플레이어를 방에 배정해준다. 이때 정원이 가득 찬 방에 플레이어를 또 넣는 것을 방지하기 위한 if문을 작성하였다.

 

    for (int i = 0; i < 301; i++) {
        // 텅 빈 방은 아직 생성되지 않은 방과 같기에
        if (room[i].size() == 0) break;

        sort(room[i].begin(), room[i].end(), compare);

        // 출력
        if (room[i].size() == m) cout << "Started!\n";
        else cout << "Waiting!\n";

        for (Player player : room[i]) 
            cout << player.level << ' ' << player.name << '\n';
    }

 생성된 방의 플레이어를 출력하는 부분의 코드이다. 방의 생성은 앞부터 순서대로 이루어지므로 탐색을 하다가 비어있는 방을 만나면 그 뒤의 방은 모두 아직 생성되지 않은 방이기에 반복문을 종료한다.