문제
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/258712
친구들끼리 카카오톡 선물하기 기능을 사용해 선물을 주고받은 이번 달까지의 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하고 싶다.
- 두 사람이 선물을 주고받은 기록이 있으면, 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물 하나를 받는다.
- 두 사람이 선물을 주고받은 기록이 없거나 그 수가 같으면, 선물 지수가 큰 사람이 작은 사람에게 선물 하나를 받는다.
- 선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값이다.
- 두 사람의 선물 지수가 같으면 다음 달에 선물을 주고받지 않는다.
위의 규칙대로 선물을 주고받을 때, 다음 달에 선물을 가장 많이 받을 친구가 받을 선물의 수를 알고 싶다.
친구들의 이름은 담은 1차원 배열 friends, 선물을 주고받은 기록을 담은 1차원 배열 gifts를 매개변수로 받아 다음 달에 받을 선물의 최고값을 반환하는 함수를 작성하라.
예시
friends = ["muzi", "ryan", "frodo", "neo"]
gifts = ["muzi frodo", "muzi frodo", "ryan muzi", "ryan muzi", "ryan muzi", "frodo muzi", "frodo ryan", "neo muzi"]
주고받은 선물을 표로 나타내면 다음과 같다.
| ↓준 사람 \ 받은 사람→ | muzi | ryan | frodo | neo |
| muzi | - | 0 | 2 | 0 |
| ryan | 3 | - | 0 | 0 |
| frodo | 1 | 1 | - | 0 |
| neo | 1 | 0 | 0 | - |
선물 지수를 표로 계산하면 다음과 같다.
| 이름 | 준 선물 | 받은 선물 | 선물 지수 |
| muzi | 2 | 5 | -3 |
| ryan | 3 | 1 | 2 |
| frodo | 2 | 2 | 0 |
| neo | 1 | 0 | 1 |
muzi는 선물을 더 많이 줬던 frodo에게서 선물 하나를 받는다.
ryan은 선물을 더 많이 줬던 muzi에게서 선물 하나를 받고, 선물 지수가 더 작은 neo에게서 선물 하나를 받는다.
frodo는 선물을 더 많이 줬던 ryan에게서 선물 하나를 받는다.
neo는 선물을 더 많이 줬던 muzi에게서 선물 하나를 받고, 선물 지수가 더 작은 frodo에게서 선물 하나를 받는다.
따라서 다음 달에 선물을 가장 많이 받는 친구의 선물의 수는 2이다.
풀이
문제의 예시로 설명해 준 대로 구현하여 풀었다. 즉, gifts로부터 주고받은 선물 정보에 대한 표를 구한 후 선물 지수를 각각 계산한다. 그리고 해당 값에 따라 받을 선물의 수를 셌다.
1. 주고받은 선물 정보에 대한 표 생성
선물 정보에 대한 표를 구하는 것은 함수로 분리했다.
friends로 전달받은 이름의 순서를 테이블의 인덱스 키로 취급했고, 각자 주고받은 수를 구한 뒤 행의 끝에 선물 지수에 대한 정보를 추가하여 반환한다.
def make_gifts_table(friends, gifts):
num_friends = len(friends)
# 선물 지수 값을 위한 공간 포함하여 테이블 초기화
table_gifts = [[0 for _ in range(num_friends + 1)] for _ in range(num_friends)]
for gift in gifts:
sender, receiver = gift.split()
table_gifts[friends.index(sender)][friends.index(receiver)] += 1
# 선물 지수 계산
for i, data in enumerate(table_gifts):
table_gifts[i][num_friends] = sum(data) - sum([row[i] for row in table_gifts])
return table_gifts
2. 다음 달에 받을 선물의 수 계산
make_gifts_table 함수로 선물을 주고받은 수와 선물 지수를 계산한 테이블을 기반으로 각자 다음 달에 받을 선물의 수를 계산한다.
참고로 다음 달에 받을 선물의 수는 테이블을 순회하면서 계산하는데, 선물을 주고받은 한 쌍이 각자 다음 달에 받을 선물의 수를 한 번에 계산하면 테이블을 순회하는 범위를 반으로 줄일 수 있다. 또한 조건문 없이 자기 자신까지 주고받는 경우는 고려하지 않도록 조정할 수 있다.
def solution(friends, gifts):
answer = 0
num_friends = len(friends)
table_gifts = make_gifts_table(friends, gifts)
# 다음 달에 받을 선물의 수
list_gifts = [0 for _ in range(num_friends)]
for i in range(num_friends):
# 순회 범위 조정
for j in range(i + 1, num_friends):
# 선물을 주고받은 기록이 있는 경우
if (table_gifts[i][j] != 0 or table_gifts[j][i] != 0) and (table_gifts[i][j] != table_gifts[j][i]):
list_gifts[i if table_gifts[i][j] > table_gifts[j][i] else j] += 1
else:
# 선물 지수 값 비교
if table_gifts[i][num_friends] > table_gifts[j][num_friends]:
list_gifts[i] += 1
elif table_gifts[i][num_friends] < table_gifts[j][num_friends]:
list_gifts[j] += 1
return max(list_gifts)
참고 문서
https://school.programmers.co.kr/learn/courses/30/lessons/258712