회전초밥_백준28107

 

<문제>

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

 

 

<시간 초과 풀이>

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pref_list = []

for _ in range(N):
    pref_menu_set = set(map(int, input().split()[1:]))
    pref_list.append(pref_menu_set)

food_list = list(map(int, input().split()))
result = [0] * N

for food in food_list:
    for i, pref_menu_set in enumerate(pref_list):
        if food in pref_menu_set:
            pref_menu_set.remove(food)
            result[i] += 1
            break

print(' '.join(map(str, result)))

 

- 손님이 원하는 초밥 리스트를 set으로 하고 손님 순서대로 배열에 담음

- 나오는 초밥을 순회하면서 손님이_원하는_초밥리스트_배열을 다시 순회 (시간초과의 원인인듯)

- 원하는_초밥리스트에 있으면 set에서 remove 후 카운트

- 그래서 나오는 초밥을 key로 한 객체를 사용해야 하나 고민

 

<gpt 풀이>

import sys

input = sys.stdin.read
data = input().split("\n")

# N: 손님 수, M: 초밥 개수
N, M = map(int, data[0].split())

# 손님별 주문 목록과 먹은 초밥 개수
customer_sushi = [set() for _ in range(N)]
customer_count = [0] * N
sushi_to_customers = {}  # {초밥 번호: 먹고 싶은 손님 리스트}

# 손님의 주문 목록을 저장
for i in range(N):
    line = list(map(int, data[i + 1].split()))
    for sushi in line[1:]:  # 첫 번째 값(k)은 필요 없음
        customer_sushi[i].add(sushi)
        if sushi not in sushi_to_customers:
            sushi_to_customers[sushi] = []
        sushi_to_customers[sushi].append(i)  # 해당 초밥을 원하는 손님 리스트에 추가

# 초밥 리스트
sushi_list = list(map(int, data[N + 1].split()))

# 초밥이 나올 때마다 처리
for sushi in sushi_list:
    if sushi in sushi_to_customers:  # 해당 초밥을 원하는 손님이 있다면
        for i in sushi_to_customers[sushi]:  # 그 손님들 중에서
            if sushi in customer_sushi[i]:  # 여전히 초밥을 먹을 수 있다면
                customer_count[i] += 1  # 초밥 개수 증가
                customer_sushi[i].remove(sushi)  # 초밥 제거
                break  # 한 명만 먹을 수 있으므로 종료

# 결과 출력
print(" ".join(map(str, customer_count)))

 

- chatGPT 풀이도 초밥을 key로 담은 객체를 사용, 손님이 원하는 초밥 리스트도 set

- 초밥이 나오는 대로 순회

- 원하는_초밥_리스트 set에서 확인하고 있으면 remove

- 그러나 초밥이 key인 객체에서 값을 빼지 않고 그냥 둬서 시간을 절약 -> 어차피 set에서만 확인하면 됨

- 통과는 됐지만 깔끔한 풀이는 아닌듯

 

 

<다른 풀이>

import sys
from collections import Counter

a = sys.stdin.read().splitlines()
t = int((a[0].split())[0])
food = a[-1].split( )
f_cnt = Counter(food)
cnt = 0
res = []
        
for i in range(1,t+1):
        data = a[i][1::].split( )
        for j in data:
            if f_cnt[j] > 0:
                f_cnt[j] -= 1
                cnt += 1
        res.append(str(cnt))
        cnt = 0
print(' '.join(res))

 

- 다른 사람 풀이

- Counter를 이용 -> 리스트 안에 요소별로 중복되는 횟수를 카운트해서 객체 저장

- 초밥이 나오는 순서가 중요한게 아니라 손님의 순서가 중요하다는 아이디어

- 초밥은 어차피 손님 순서대로 소진하게 되어 있음

- 손님의 초밥 리스트를 순회하면서 나왔던 초밥들을 하나씩 제거하고 카운트

- 어떤 순서가 중요한지 생각하는 것이 포인트, 자료구조는 그 다음