프로그래머스 Level 1 | 가장 많이 받은 선물 | Python

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258712

---

문제 파악

“다음 달에 가장 많이 선물을 받는 친구가 몇 개를 받는지” 구하는 문제.

규칙 정리:

1) 두 사람 사이에 주고받은 기록이 있고 서로 준 개수가 다르면
→ 더 많이 준 쪽이 다음 달에 1개 받음

2) 두 사람 사이에 기록이 없거나 서로 준 개수가 같으면
→ 선물 지수(준 개수 − 받은 개수)가 큰 쪽이 1개 받음

3) 선물 지수도 같으면
→ 아무도 안 받음

선물 지수 예: 3개 주고 10개 받았으면 3 - 10 = -7.

입력:

• friends: 친구 이름 리스트 (예: ["muzi", "ryan", "frodo", "neo"])
• gifts: "A B" 형식 문자열 리스트 (A가 B에게 선물함)

---

어떻게 풀까

처음엔 중첩 딕셔너리로 given["muzi"]["frodo"] = 2 같은 구조가 떠오른다.
하지만 중첩 딕셔너리의 단점이 있다:

• 키 존재 체크/초기화 코드가 번거롭다 (if a not in given: given[a]={} ...).
• a→b와 b→a를 쌍으로 비교할 때 매번 get(..., 0)을 써야 한다.
• 이름이 문자열이라 탐색/인덱싱 비용과 코드 복잡도가 늘어난다.
• N이 커질수록 타입 혼재/오타에 취약하다.

그래서 정석은 이름을 숫자 인덱스(0..N-1)로 매핑하고,
관계를 2차원 리스트(행렬)로 관리하는 것:

• idx[name] = i 이름 → 인덱스
• given[i][j] = i가 j에게 준 횟수 (N×N)
• out_cnt[i], in_cnt[i]로 총합 관리 → gift_index[i] = out_cnt[i] - in_cnt[i]
• 모든 쌍 (i, j)는 i < j 한 번만 비교

---

해답 및 풀이

def solution(friends, gifts):
    n = len(friends)
    
    # 1) 이름 → 인덱스 매핑
    idx = {}
    for i, name in enumerate(friends):
        idx[name] = i

    # 2) 관계/총합 구조
    given = [[0] * n for _ in range(n)]  # given[i][j] = i가 j에게 준 횟수
    out_cnt = [0] * n                    # i가 준 총합
    in_cnt = [0] * n                     # i가 받은 총합

    # 3) 기록 적재
    for g in gifts:
        a, b = g.split()
        ai, bi = idx[a], idx[b]
        given[ai][bi] += 1
        out_cnt[ai] += 1
        in_cnt[bi] += 1

    # 4) 선물 지수
    gift_index = [0] * n
    for i in range(n):
        gift_index[i] = out_cnt[i] - in_cnt[i]

    # 5) 다음 달 받을 개수 계산 (쌍 비교는 i<j 한 번만)
    receive = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if given[i][j] > given[j][i]:
                receive[i] += 1
            elif given[i][j] < given[j][i]:
                receive[j] += 1
            else:
                if gift_index[i] > gift_index[j]:
                    receive[i] += 1
                elif gift_index[i] < gift_index[j]:
                    receive[j] += 1
                # 같으면 아무도 안 받음

    # 6) 최댓값 반환
    return max(receive) if receive else 0