[백준/Python] 25757 - 임스와 함께하는 미니게임

문제

임스가 미니게임을 같이할 사람을 찾고 있습니다.

플레이할 미니게임으로는 윷놀이
$Y$, 같은 그림 찾기 $F$, 원카드 $O$가 있습니다. 각각 2, 3, 4 명이서 플레이하는 게임이며 인원수가 부족하면 게임을 시작할 수 없습니다.

사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 임스가 플레이할 게임의 종류가 주어질 때, 최대 몇 번이나 임스와 함께 게임을 플레이할 수 있는지 구하시오.

임스와 여러 번 미니게임을 플레이하고자 하는 사람이 있으나, 임스는 한 번 같이 플레이한 사람과는 다시 플레이하지 않습니다.

임스와 함께 플레이하고자 하는 사람 중 동명이인은 존재하지 않습니다. 임스와 lms0806은 서로 다른 인물입니다.

입력

첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 

두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들의 이름이 문자열로 주어진다. $(1 \le$ 문자열 길이 $\le 20)$ 

사람들의 이름은 숫자 또는 영문 대소문자로 구성되어 있다.

출력

임스가 최대로 몇 번이나 게임을 플레이할 수 있는지 구하시오.

풀이
n의 최대 크기가 100,000이기 때문에 최대 $O(nlogn)$의 시간복잡도까지 허용된다
보통 리스트를 순회하는 데서 $O(n)$시간이 소요되기 때문에 이를 줄이고자 Dict를 사용했다
초기에는 하나의 dict를 사용해서 과거에 게임했던 사람의 명단을 리스트로 관리했지만 in을 사용하게되면 리스트 순회가 발생하기 때문에 dict를 두 개 사용했다

게임 별로 필요로하는 인원 수가 다르기 때문에 게임별 필요 인원 수를 저장하는 dict와 과거에 게임했던 사람의 이름을 key로 하고 bool값을 value로 하는 dict를 하나 더 사용했다

for문을 돌며 이름을 입력을 받음과 동시에 과거 전적 명단의 dict에 해당 이름이 있는지 체크하는 과정을 try except로 구현했다
dict에 해당 이름을 key로 주고 검색했을 때 과거 전적이 없다면 keyerror가 발생하는 점을 이용한다 이후 except 구문에서 해당 이름을 dict에 추가하고 현재까지 모은 인원을 +1 해준 후에 필요 인원 수가 충족됐는지 검사한다
만약 에러가 발생하지 않으면 이미 과거에 함께 게임한 전적이 있는 사람이므로 pass한다

코드

import sys

n, game = sys.stdin.readline().split()
n = int(n)

info = dict()
info["Y"] = 2
info["F"] = 3
info["O"] = 4

names = dict()

cnt = 0
num = 1
for _ in range(n):
    name = sys.stdin.readline().strip()
    try:
        if names[name]:
            pass
    except:
        names[name] = True
        num += 1
        if info[game] == num:
            cnt += 1
            num = 1
print(cnt)