[백준] 20006 랭킹전 대기열

문제 설명

문제 링크

이번 문제는 게임의 랭킹전 매치메이킹을 구현하는 것과 비슷한(혹은 비슷하다고 주장하는) 문제이다. 실제로 모션비트 프로젝트를 진행할 때, 이와 비슷한 형태로 매치메이킹을 구현을 했어서 그런지 꽤 흥미로웠다.

우선 주어진 정보를 확인하면, 총 플레이어의 수와 각 방의 최대 인원이 주어진다. 문제에서 설명하는 게임의 매치메이킹 시스템은 방장의 레벨을 기준으로 하며, 방장 레벨 기준 +- 10 범위 내의 플레이어들을 방에 넣어준다. 최종적으로 방의 정보와 같이 해당 방의 인원들을 출력해주면 된다.

문제 풀이

주어진 조건들에 조건문을 설정, 이에 맞게 분기하여 넣어주면 된다.

문제에서 주어진 조건:

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

이를 풀어서 보면 다음과 같다:

1. 들어갈 수 있는 방(방장의 레벨이 플레이어의 레벨과 +-10 범위 내인 경우)이 있다면 해당 방에 플레이어를 넣고, 없다면 방을 생성한다.
2. 방의 정원이 모두 차면 해당 방에는 입장 불가능하다.
3. 들어갈 수 있는 방이 있다면 먼저 생성된 방에 들어간다.

우선, 방이 없으면(첫 플레이어) 무조건 방을 생성한다.

l, n = map(str, input().split())
l = int(l)
rooms.append([(l, n)])

for _ in range(1, p):
  블라블라

풀고 나서 생각해보니 위와 같이 첫 플레이어 한정 분기를 해주면 시간적으로 이득을 볼 수도 있을 것 같다.

매치메이킹 기준에 따른 조건문을 설정해준다.

if l-10 <= level and l + 10 >= level

방 정원은 문제에서 m으로 주어지는데, 이 또한 조건문을 설정해주면 된다.

if l-10 <= level and l + 10 >= level and len(rooms[j]) < m:

위의 조건문들로 입장 가능한 방이 판별되면 해당 방에 플레이어를 넣어주면 된다.

다 넣어주고 난 후에, 방의 인원이 정원과 같으면 Started!를 출력하고, 방이 정원 미달이면 Waiting!을 출력해주면 된다. 이 때, 문제에서 ‘플레이어의 정보는 닉네임이 사전순으로 앞서는 플레이어부터 출력한다’ 라는 조건이 주어졌기 때문에 Sorted()함수를 통해 배열을 정렬해준다.

for k in range(len(rooms)):
    if len(rooms[k]) == m:
        print("Started!")
    else: 
        print("Waiting!")
    players = sorted(rooms[k], key=lambda x: x[1])
    for player in players:
        print(*player)

코드

import sys

input = sys.stdin.readline

p, m = map(int, input().split())
rooms = []


for _ in range(p):
    l, n = map(str, input().split())
    l = int(l)
    made = False
    if not rooms:
        rooms.append([(l, n)])
    else:
        for j in range(len(rooms)):
            level, nickname = rooms[j][0]
            if l-10 <= level and l + 10 >= level and len(rooms[j]) < m:
                rooms[j].append((l, n))
                made = True
                break
        if not made:
            rooms.append([(l,n)])    

for k in range(len(rooms)):
    if len(rooms[k]) == m:
        print("Started!")
    else: 
        print("Waiting!")
    players = sorted(rooms[k], key=lambda x: x[1])
    for player in players:
        print(*player)