1. 문제
회전 초밥 가게에 N명의 손님이 있고, 요리사는 M개의 초밥을 순서대로 만든다. 요리사가 초밥을 만들 경우, 1번 손님부터 N번 손님의 순서대로 그 초밥을 받게 된다. 만약 먼저 초밥을 받는 손님이 초밥을 먹을 경우, 뒤의 손님들은 해당 초밥을 먹을 수 없다. 만약 아무도 해당 초밥을 먹지 않는다면, 초밥은 버려진다.
N명의 손님은 각자 먹고 싶은 초밥이 적힌 주문 목록을 가지고 있다. 목록에 적힌 초밥의 순서에 상관 없이 만약 목록에 적혀있는 초밥이 앞에 오면 반드시 먹는다. 만약, 목록에 적히지 않은 초밥을 받는다면 그 초밥은 반드시 먹지 않는다. 단, 손님들은 다양한 초밥을 먹고 싶어하기 때문에 각 종류의 초밥은 최대 한 번만 먹는다.
각 손님의 주문 목록과 순서대로 만들어지는 M개의 초밥이 주어질 때, 각 손님이 먹게 되는 초밥의 개수를 구해 보자.
입력
첫 번째 줄에 손님의 수 N과 초밥의 수 M이 공백으로 구분되어 주어진다. (1≤N≤100 000;1≤M≤200000)
두 번째 줄부터 N개의 줄에 걸쳐 각 손님에 대한 주문 목록을 나타내는 정수 k와 A1,A2,…,Ak가 공백으로 구분되어 순서대로 주어진다. k는 주문 목록에 적힌 초밥 종류의 개수이며, Ai는 주문 목록에 적힌 초밥 종류이다. (1≤Ai≤200000)
각 손님의 주문 목록에 적힌 초밥 종류는 모두 다르며, 모든 손님에 대해 k의 합이 200000이하임이 보장된다.
N+2번째 줄에 요리되는 초밥의 종류를 나타내는 M개의 정수 B1,B2,…,BM이 공백으로 구분되어 순서대로 주어진다. (1≤Bi≤200000)
출력
한 줄에 N개의 정수 C1,C2,…CN을 공백으로 구분하여 출력한다. Ci번 손님이 먹은 초밥의 개수를 의미한다.
2. 정답 코드
# @Date : 2024-09-04 19:30:41
# @Author : ecodev
# @Link : http://ecodev-blog.vercel.app
import sys
input = sys.stdin.readline
############ ---- Input Functions ---- ############
def inp():
return(int(input()))
def inlt():
return(list(map(int, input().split())))
def insr():
s = input()
return(list(s[:len(s) - 1]))
def invr():
return(map(int, input().split()))
n, m = invr()
dic = {}
result = [0] * n
for i in range(n):
ls = inlt()
for j in range(1, len(ls)):
if ls[j] in dic:
dic[ls[j]].append(i)
else:
dic[ls[j]] = [i]
sushi = inlt()
for i in sushi:
if i in dic and dic[i]:
result[dic[i].pop(0)] += 1
print(*result)
3. 생각한 방향 및 설명
- brute-force한 방법으로 풀 수 있을까?
→ 즉 초밥이 들어올 때마다 for문을 이용해 계속 손님리스트를 탐색한다는 말인데 최악의 경우
O(N * M)이 나올 수 있기 때문에 시간초과가 날 것이다.- 그렇다면 어떻게해야 시간을 줄일 수 있을까?
우선 내 눈에는 이런 구조가 보였다.
0번 손님 : [1, 6], 1번 손님 : [2, 3, 5] … 이런식으로 dictionary를 만들생각을 했었다. 하지만 마찬가지로 0번손님이 우선해서 먹을 수 있기 때문에 for문과 마찬가지의 탐색시간이 걸릴 것이다.그렇다면 그 반대는?
1번 음식 : [0번손님, 2번손님], 2번 음식 : [2번손님]… 이런식으로 만들면 파이썬의 dictionary의 조회 즉 in 연산, 특정 key의 value값 찾는 연산은 모두 O(1)시간에 수행된다. 그리고 각 음식의 value리스트 즉 [0번손님, 2번손님]이런 리스트는 처음 설정해줄 때 for문으로 처음부터 받고 있기 때문에 먼저 온 손님이 리스트의 가장 처음으로 갈 것이다. 따라서 초밥리스트를 처음부터 보면서 만약 dictionary에 해당 초밥이 존재하면 그 초밥을 key로 갖는 value 리스트의 첫번째 원소를 빼주면 손님의 순서대로 받을 수 있게 된다. 또한 한번 더 같은 초밥을 먹을 수 없기 때문에 pop해주면 깔끔하겠다.
이렇게 푸는게 맞나?생각하며 알고리즘 분류를 보니 우선순위 큐로 푸는 문제였다.
하지만 시간초과가 나지않고, 알고리즘 로직에 문제가 없다면 어떤 풀이든 돌아만 가게 짜보자.
오히려 알고리즘 분류를 보고 문제를 풀면 고정관념에 사로잡혀 코드의 다양성을 해칠 수 있는 것 같다.