백준 20006 - 랭킹전 대기열

문제 설명

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

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 조건에 따라 플레이어를 매칭하는 방을 만들어 관리하는 프로그램을 작성하는 것이다.

플레이어의 매칭 조건은 다음과 같다.

• 입장할 방이 없으면 새로 생성한다.
• 방에 입장하는 조건은 첫번째로 입장한 플레이어의 레벨 ±10이다.
• 입장가능한 방이 여러개라면 먼저 생성된 방에 입장한다.

 

해당 문제는 방을 관리하는 구조체를 생성하여 풀면 간단하다.

해당 구조체에서는 입장가능한 레벨, 입장한 플레이어의 정보를 관리해 주면 된다.

방의 입장과 마지막에 출력을 위한 함수를 이용하면 더욱 간단하게 해결할 수 있다.

struct Room
{
    Room(int level, string nickname)
    {
        minLevel = level - 10;
        maxLevel = level + 10;

        players.push_back({ level, nickname });
    }

    int minLevel;
    int maxLevel;

    vector<pair<int, string>> players;

    bool Enter(int level, string nickname)
    {
        if (level < minLevel || level > maxLevel) return false;
        if (players.size() == m) return false;

        players.push_back({ level, nickname });
        return true;
    }

    void print()
    {
        if (players.size() == m) cout << "Started!\n";
        else cout << "Waiting!\n";

        sort(players.begin(), players.end(), cmp);

        for (auto [level, nickname] : players)
        {
            cout << level << " " << nickname << "\n";
        }
    }
};

생성자에서 처음 입장하는 플레이어의 레벨과 닉네임을 통해 방의 기본정보를 초기화한다.

방에 입장을 수행하고 입장 여부를 반환하는 함수 Enter를 보면 조건에 따라 결과를 반환하는 것을 볼 수 있다.

 

위와 같은 구조체를 준비했다면 플레이어의 정보를 입력으로 받아와 먼저 생성된 방부터 살펴보며 입장할 수 있는지 확인하면 된다.

vector<Room> rooms;
for (int i = 0; i < p; i++)
{
    cin >> l >> n;

    bool bEnter = false;
    for (auto& room : rooms)
    {
        bEnter = room.Enter(l, n);
        if (bEnter) break;
    }

    if (!bEnter)
    {
        Room newRoom(l, n);
        rooms.push_back(newRoom);
    }
}

범위 기반 for문과 auto를 사용할 때 주의해야 할 점은 auto에서 참조를 통해 객체를 가져오지 않는다면 복사연산이 일어나기 때문에 원하는 대로 동작하지 않는다. (복사본에 대해 Enter를 수행함 = 원본은 변하지 않음)

 

모든 과정이 끝났다면 존재하는 모든 방에 대해 출력을 진행하면 된다.

for (auto room : rooms)
{
    room.print();
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>

using namespace std;

int p, l, m;
string n;

bool cmp(const pair<int, string>& a, const pair<int, string>& b)
{
    return a.second < b.second;
}

struct Room
{
    Room(int level, string nickname)
    {
        minLevel = level - 10;
        maxLevel = level + 10;

        players.push_back({ level, nickname });
    }

    int minLevel;
    int maxLevel;

    vector<pair<int, string>> players;

    bool Enter(int level, string nickname)
    {
        if (level < minLevel || level > maxLevel) return false;
        if (players.size() == m) return false;

        players.push_back({ level, nickname });
        return true;
    }

    void print()
    {
        if (players.size() == m) cout << "Started!\n";
        else cout << "Waiting!\n";

        sort(players.begin(), players.end(), cmp);

        for (auto [level, nickname] : players)
        {
            cout << level << " " << nickname << "\n";
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> p >> m;

    vector<Room> rooms;
    for (int i = 0; i < p; i++)
    {
        cin >> l >> n;

        bool bEnter = false;
        for (auto& room : rooms)
        {
            bEnter = room.Enter(l, n);
            if (bEnter) break;
        }

        if (!bEnter)
        {
            Room newRoom(l, n);
            rooms.push_back(newRoom);
        }
    }

    for (auto room : rooms)
    {
        room.print();
    }

    return 0;
}

---