백준 20006번 [랭킹전 대기열](C++) -yes6686- 티스토리

백준 문제 풀이: 20006 [랭킹전 대기열]

---

문제 링크: https://www.acmicpc.net/problem/20006

문제 설명:

랭킹전 대기열을 관리하는 시스템을 구현하는 문제입니다. 플레이어는 자신의 레벨을 기준으로 방에 배정되며, 방이 꽉 차면 게임이 시작됩니다.

방은 다음 조건을 충족해야 합니다:

• 빈 방이 있다면 먼저 들어간다.
• 방이 꽉 차지 않았다면, 기존 방의 첫 번째 플레이어와 레벨 차이가 10 이하인 경우 같은 방에 들어갈 수 있다.
• 위 조건을 만족하지 못하면 새로운 방을 만든다.

---

문제 해결 코드

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

vector<pair<int, string>> rooms[301]; // 대기방 리스트

// 닉네임을 기준으로 오름차순 정렬
bool compare(pair<int, string> a, pair<int, string> b) {
    return a.second < b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int p, m;
    cin >> p >> m; // 플레이어 수, 최대 방 크기 입력

    for (int i = 0; i < p; i++) {
        int level;
        string nickname;
        cin >> level >> nickname;

        // 적절한 방 찾기
        for (int j = 0; j < p; j++) {
            if (rooms[j].size() >= m) continue; // 방이 꽉 찼으면 건너뛴다.
            if (rooms[j].empty()) { // 방이 비어있으면 새로운 방을 만든다.
                rooms[j].push_back({ level, nickname });
                break;
            }
            if (abs(rooms[j].front().first - level) > 10) continue; // 레벨 차이가 10 초과면 다른 방 찾기
            rooms[j].push_back({ level, nickname });
            break;
        }
    }

    // 결과 출력
    for (int i = 0; i < p; i++) {
        if (rooms[i].size() == 0) break; // 비어있는 방이면 종료
        if (rooms[i].size() == m) {
            cout << "Started!" << '\n'; // 방이 꽉 찼다면 시작
        } else {
            cout << "Waiting!" << '\n'; // 대기 중
        }

        // 닉네임 기준 정렬 후 출력
        sort(rooms[i].begin(), rooms[i].end(), compare);
        for (int j = 0; j < rooms[i].size(); j++) {
            cout << rooms[i][j].first << " " << rooms[i][j].second << '\n';
        }
    }
}

예제 입력:

6 2
10 a
15 b
20 c
25 d
30 e
35 f

예제 출력:

Started!
10 a
15 b
Started!
20 c
25 d
Started!
30 e
35 f

---

코드 설명

• 핵심 알고리즘: 벡터를 활용한 대기방 관리
• 구현 세부사항:
  • 각 방은 벡터를 이용해 저장되며, 레벨이 비슷한 플레이어를 같은 방에 배치
  • 닉네임을 기준으로 오름차순 정렬 후 출력
  • 방이 최대 인원 수(m)에 도달하면 "Started!"를 출력
  • 대기 중인 경우 "Waiting!"을 출력
• 시간 복잡도: O(P log P), 각 방 내의 정렬 연산 포함

---

결과

플레이어가 레벨 기준으로 방에 배정되고, 방이 꽉 차면 게임이 시작됩니다. 벡터를 활용한 대기열 관리 문제를 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!