백준 20006 랭킹전 대기열 Python

🐸 문제 정보

20006번: 랭킹전 대기열

 

🤖 알고리즘

구현

 

⏱️ 풀이 시간

23.15m

 

📝 풀이

언뜻 보면 굉장히 쉬운 구현 문제이지만, 엄청난 함정이 하나 있었다. (아닐지도 모른다)

나는 처음에 딕셔너리를 이용해서 풀었는데, 예시로 나와있는 테스트 케이스는 통과되지만 4%쯤에서 틀리게된다.

이유는 같은 레벨의 다른 닉네임의 사람이 들어오는 경우, 딕셔너리에 있는 리스트가 덮어씌워지기 때문이다.

만약 비슷하게 풀었고 틀린다면 아례 반례를 입력해보는 것도 좋을 것 같다.

 

여튼 이 문제는 딕셔너리가 아닌 리스트로 풀면 쉽게 풀 수 있다.

딕셔너리가 보기에는 직관적이지만, 위의 문제를 해결하려면 비용이 너무 많이 드니 리스트로 풀자.

 

반례 (질문게시판에서 찾았다.)

11 5
10 a
15 b
20 c
25 d
30 e
17 f
18 g
26 h
24 i
28 j
10 k

 

틀린 답

import sys
from collections import defaultdict
input = sys.stdin.readline

p, m = list(map(int, input().rstrip().split()))
rooms = defaultdict(list)

for _ in range(p):
    lev, name = list(input().rstrip().split())
    lev = int(lev)
    flag = False
    for key in rooms.keys():
        if key - 10 <= lev <= key + 10:
            if len(rooms[key]) < m:
                rooms[key].append((lev, name))
                flag = True
                break
    if not flag:
        rooms[lev].append((lev, name))

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

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

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

for _ in range(p):
    lev, name = list(input().rstrip().split())
    lev = int(lev)
    flag = False
    for room in rooms:
        key = room[0][0] # 기준 레벨
        if key - 10 <= lev <= key + 10:
            if len(room) < m:
                room.append((lev, name))
                flag = True
                break
    if not flag:
        rooms.append([(lev, name)])

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