latentspace.world

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

문제 설명

임스가 다른 사람들과 미니게임을 함께 플레이하려고 한다.
플레이할 수 있는 게임은 세 종류:
- 윷놀이(Y): 2명이 필요 (임스 포함)
- 같은 그림 찾기(F): 3명이 필요 (임스 포함)
- 원카드(O): 4명이 필요 (임스 포함)
여러 사람(N 명)이 임스와 게임하기를 신청
임스는 한 번 같이 플레이한 사람과는 다시 플레이하지 않음

임스가 최대로 몇 번 게임을 플레이할 수 있는지 계산하는 것이다.

문제 분석

이 문제의 해법을 찾기 위해서는 아래를 고려해야 한다.

임스를 제외하고 필요한 인원은 각각 윷놀이 1명, 같은 그림 찾기 2명, 원카드 3명이다.
1. 이 부분을 바로 캐치하지 못해 푸는 데 10분 정도 더 걸렸다;;
동일한 사람이 여러 번 신청할 수 있지만, 실제로는 한 번만 게임에 참여할 수 있다.
결국 사용 가능한 서로 다른 사람들의 수를 게임당 필요한 인원수로 나누면 된다.

코드 구현

import sys

input = sys.stdin.readline

# 각 게임 유형별로 임스를 제외하고 필요한 인원 수
games = {
    "Y": 1,  # 윷놀이: 임스 + 1명
    "F": 2,  # 같은 그림 찾기: 임스 + 2명
    "O": 3,  # 원카드: 임스 + 3명
}

def solution():
    n, kind_of_game = input().split()
    n = int(n)

    # 중복 제거를 위한 집합(set) 자료구조 사용
    usernames = set()
    for _ in range(n):
        usernames.add(input().strip())  # 줄바꿈 문자 제거. 안 해도 상관 없다.

    # 최대 게임 횟수 계산: 고유한 사람 수 // 게임당 필요한 인원 수
    print(len(usernames) // games[kind_of_game])

if __name__ == '__main__':
    solution()

시간 복잡도

이 문제의 시간 복잡도는 O(N)이다. 여기서 N은 신청 횟수이다.
집합(set)에 요소를 추가하는 연산은 평균적으로 O(1)이므로, N번의 추가 연산에 대해 총 O(N)의 시간이 소요된다.

공간 복잡도

이 문제의 공간 복잡도는 O(K)이다. 여기서 K는 중복을 제거한 후의 고유한 사람 수이다.
최악의 경우 모든 신청자가 서로 다른 사람인 경우를 고려할 수 있는데, 이는 K = N이 되어 O(N)의 공간이 필요하게 된다.