백준 20006번 - 랭킹전 대기열 (C++)

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

20006번: 랭킹전 대기열

 

처음에는 정렬을 해두고 풀어도 되는 줄 알았는데 순서대로 게임을 진행해야하는 조건이 있었다. (진짜 문제좀 잘 읽자)

 

그리디 , 구현 문제였다. 처음에는 우선순위큐 문제인가 생각했는데 기준이 달라지는 것이 아니기 때문에 우선순위큐는 필요없다. 

 

나는 게임방의 기준을 rooms 벡터에 담아두고 어차피 순서가 바뀌지 않기 때문에 그 순서대로 다음 레벨을 비교해서 문제를 풀었다. 

 

구현을 연습하는데 좋은 문제였다. 그리고 큐, 우선순위큐 문제와 이 문제가 다른 이유를 비교해보는 것도 좋은 접근법이 될 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;

vector<pair<int, string>> players;
vector<int> rooms;
vector<pair<int, string>> games[501];

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

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

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int l;
		string name;
		cin >> l >> name;

		players.push_back({ l, name });
	}

	rooms.push_back(players[0].first);
	games[0].push_back(players[0]);

	for (int i = 1; i < N; i++) {
		int now_Level = players[i].first;
		bool flag = true;
		for (int j = 0; j < rooms.size(); j++) {
			if (abs(rooms[j] - now_Level) <= 10) {
				if (games[j].size() < M) {
					games[j].push_back(players[i]);
					flag = false;
					break;
				}
			}
			if (flag == false) break;
		}

		if (flag) {
			rooms.push_back(players[i].first);
			games[rooms.size() - 1].push_back(players[i]);
		}
	}

	for (int i = 0; i < rooms.size(); i++) {
		sort(games[i].begin(), games[i].end(), comp);
		if (games[i].size() == M) {
			cout << "Started!" << '\n';
		}
		else {
			cout << "Waiting!" << '\n';
		}

		for (auto a : games[i]) {
			cout << a.first << " " << a.second << '\n';
		}
	}
}