가장 많이 받은 선물
2024 카카오 윈터 인턴쉽 문제가 오픈되어 풀어보았다.
문제 설명
- 선물을 받은 사람과 선물을 준 사람이 있다.
- 선물 기록을 토대로 가장 많이 선물을 받은 사람을 구하라
가장 많이 선물을 받은 사람을 반환해라
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
다음 달 선물을 받은 사람은 어떻게 구할 수 있을까?
A 와 B 가 있을 때 선물을 더 많이 준 사람이 선물을 받는다.
선물을 더 많이 준 사람은 어떻게 구할 수 있을까?
아래와 같은 자료구조로 만들어서 선물을 비교할 수 있다.
[A] : {
[B]: 1,
[C]: 2,
[D]: 3
}
값 추출을 어떻게 해?
friends 를 기준으로 이중 for 문을 돌려서 값을 추출한다.
gift_index[a][b] 와 gift_index[b][a] 를 비교해서 값을 추출할 수 있다.
8자 그래프의 경우 간선이 2개 나올 경우 이른 리턴을 하면 된다.
from collections import defaultdict
def solution(friends, gifts):
give_dict = defaultdict(dict)
gift_index = defaultdict(int)
for gift in gifts:
a, b = gift.split(" ")
if b not in give_dict[a]:
give_dict[a][b] = 1
else:
give_dict[a][b] += 1
gift_index[a] += 1
gift_index[b] -= 1
predict_dict = defaultdict(int)
for friend_a in friends:
for friend_b in friends:
if friend_a == friend_b:
continue
if friend_b not in give_dict[friend_a]:
give_dict[friend_a][friend_b] = 0
if friend_a not in give_dict[friend_b]:
give_dict[friend_b][friend_a] = 0
if give_dict[friend_a][friend_b] > give_dict[friend_b][friend_a]:
predict_dict[friend_a] += 1
elif give_dict[friend_a][friend_b] == give_dict[friend_b][friend_a]:
if gift_index[friend_a] > gift_index[friend_b]:
predict_dict[friend_a] += 1
if not predict_dict.items():
return 0
return max([v for k, v in predict_dict.items()])
print(solution(["muzi", "ryan", "frodo", "neo"], [
"muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"]),
2)
print(solution(["joy", "brad", "alessandro", "conan", "david"], [
"alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"]), 4)
print(solution(["a", "b", "c"], ["a b", "b a", "c a", "a c", "a c", "c a"]), 0)