문제 설명
•
이번 달 선물 기록을 바탕으로 다음 달에 누가 선물을 가장 많이 받을지 예측하여, 가장 많이 친구가 받을 선물 수를 구하는 문제
◦
두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받는다.
◦
두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받는다.
▪
선물 지수: 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값
▪
만약 두 사람의 선물 지수도 같다면 다음 달에 선물을 주고받지 않는다.
예제 입력/출력
friends | gifts | result |
["muzi", "ryan", "frodo", "neo"] | ["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"] | 2 |
["joy", "brad", "alessandro", "conan", "david"] | ["alessandro brad", "alessandro joy", "alessandro conan", "david alessandro", "alessandro david"] | 4 |
["a", "b", "c"] | ["a b", "b a", "c a", "a c", "a c", "c a"] | 0 |
제약 조건
•
•
◦
gifts의 원소는 "A B"형태의 문자열
◦
A는 선물을 준 친구의 이름
◦
B는 선물을 받은 친구의 이름
문제 풀이
•
브루트 포스 -
◦
문제에서 시키는 대로 구현하면 되는 단순 구현 문제에 해당
◦
다음 자료구조들을 잘 갱신해주면 된다.
1.
N명의 친구들 간 선물 주고받은 기록을 갱신하는 gift_matrix (2차원 배열)
2.
N명의 친구들의 선물 지수를 관리하는 gift_score (1차원 배열)
풀이 코드
def solution(friends, gifts):
N = len(friends)
I = {name: index for index, name in enumerate(friends)}
gift_matrix = [[0 for _ in range(N)] for _ in range(N)]
gift_score = [0] * N
# 주고 받은 기록 갱신
for gift in gifts:
a, b = gift.split()
gift_matrix[I[a]][I[b]] += 1
gift_score[I[a]] += 1
gift_score[I[b]] -= 1
answers = [0] * N
for a in range(N):
for b in range(N):
if a == b:
continue
# Case 1. 이번 달에 a가 b에게 선물을 더 많이 줬다면
case1 = (gift_matrix[a][b] > gift_matrix[b][a])
# Case 2. a와 b의 선물 주고 받은 개수가 같고, 선물 지수가 a가 더 높다면
case2 = (gift_matrix[a][b] == gift_matrix[b][a] and gift_score[a] > gift_score[b])
answers[a] += (case1 or case2)
return max(answers)
Python
복사