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))
import sys
import heapq
input = sys.stdin.readline
N = int(input())
heap = []
m_dict = {}
for _ in range(N):
x = int(input())
if x != 0: # push
if x > 0: # x가 양수일 경우
heapq.heappush(heap, x)
else: # x가 음수일 경우
heapq.heappush(heap, -x)
if -x in m_dict:
m_dict[-x] += 1
else:
m_dict[-x] = 1
else: # pop
if len(heap) == 0: # 배열이 비어있는 경우
print(0)
else: # 비어있지 않은 경우
min = heapq.heappop(heap)
if min in m_dict: # 미리 저장해둔 마이너스 딕셔너리에 min값에 해당하는 값이 존재하면
print(-min)
m_dict[min] -= 1
if m_dict[min] == 0: # 하나 뽑아서 마이너스 딕셔너리에 해당 키의 값이 0이 되었을때
del m_dict[min]
else:
print(min)
import heapq
class Solution:
def findRelativeRanks(self, score: List[int]) -> List[str]:
result = [None] * len(score)
heap = [-n for n in score]
heapq.heapify(heap)
for i in range(1, len(score)+1):
biggest = -heapq.heappop(heap)
idx = score.index(biggest)
if i == 1:
result[idx] = 'Gold Medal'
elif i == 2:
result[idx] = 'Silver Medal'
elif i == 3:
result[idx] = 'Bronze Medal'
else:
result[idx] = str(i)
return result
- 큰 숫자 순서대로 뽑는 것을 생각해서 heap 사용
- 리스트 변환 O(N), heapify O(N)
- heappop(heap) O(log N), index 찾는 부분 O(N) -> 반복문까지 O(N * (N + log N)) = O(N2)
- 전체 시간복잡도는 O(N2)
이번엔 해시테이블로 접근
class Solution:
def findRelativeRanks(self, score: List[int]) -> List[str]:
sorted_score = sorted(score, reverse=True)
rank_map = {val:i for i, val in enumerate(sorted_score)}
ans = []
for val in score:
rank = self.convert_rank(rank_map[val])
ans.append(rank)
return ans
def convert_rank(self, idx):
if idx == 0:
return "Gold Medal"
elif idx == 1:
return "Silver Medal"
elif idx == 2:
return "Bronze Medal"
else:
return str(idx + 1)
import sys
input = sys.stdin.read().splitlines()
pair = {
')' : '(',
']' : '['
}
res = []
for str in input:
if str == '.':
break
stack = []
for s in str:
if s == '(' or s == '[':
stack.append(s)
elif s == ')' or s == ']':
if len(stack) == 0:
res.append('no')
break
prev_el = stack.pop()
if prev_el != pair[s]:
res.append('no')
break
elif s == '.':
res.append('yes') if len(stack) == 0 else res.append('no')
print('\n'.join(res))
- 비슷한 문제를 많이 풀어봐서 짝 맞추는 건 stack과 pair 해시테이블을 써야겠다고 생각
- 문자열의 문자를 반복하는데 짝의 앞의 것이 오는 경우, 짝의 뒤의 것이 오는 경우, 끝나는 경우 (.)를 나눠서 진행
