가장 많이 받은 선물

문제 보기 · Level 1 · 2024 KAKAO WINTER INTERNSHIP · 정답률 31% · 푼 사람 19,301명 (2026-09-30 기준)¹

문제

친구들이 이번 달까지 주고받은 선물 기록으로 다음 달 선물을 예측한다. 두 사람 사이에서 더 많이 준 사람이 선물을 하나 받는다. 주고받은 수가 같거나 기록이 없으면 선물 지수(준 수 − 받은 수)가 큰 사람이 받는다. 선물 지수까지 같으면 주고받지 않는다. 다음 달에 가장 많이 받는 사람이 받을 선물 수를 돌려준다.

친구 2~50명
선물 기록 최대 10,000개

풀이

막히면 한 단계씩 펼친다.

필요한 개념

딕셔너리와 집합: 이름을 번호로 바꾸는 표
리스트와 문자열: “누가 누구에게 몇 개”를 적는 2차원 리스트
순열과 조합: 친구가 n명이면 두 사람 짝은 순서가 없는 조합이라 \(\binom{n}{2} = \frac{n(n-1)}{2}\)개다.

1단계 · 작은 예로 손으로 풀기

친구 [a, b, c], 기록 [“a b”, “a b”, “b a”, “c a”]

누가 누구에게 몇 개 줬는지 표로 적는다(줄이 준 사람, 칸이 받은 사람).

준 \ 받은	a	b	c
a	-	2	0
b	1	-	0
c	1	0	-

선물 지수 = 준 수 − 받은 수: a = 2 − 2 = 0, b = 1 − 2 = −1, c = 1 − 0 = 1

두 사람씩 짝지어 규칙을 적용한다.

a와 b: a가 2개, b가 1개 줬다 → a가 받는다
a와 c: a가 0개, c가 1개 줬다 → c가 받는다
b와 c: 서로 0개로 같다 → 지수가 큰 c(1 > −1)가 받는다

다음 달: a 1개, b 0개, c 2개 → 답 2

2단계 · 가장 단순한 방법과 그 속도

1단계 그대로 하면 된다. 표를 채우는 데 기록 1만 개를 한 번 훑고, 짝은 최대 50 × 49 / 2 = 1,225쌍이다. 아주 빠르다. 이 문제도 어려움은 규칙을 정확히 옮기는 데 있다.

3단계 · 핵심 아이디어

이름을 0, 1, 2, … 번호로 바꾸는 딕셔너리를 만든다. 그러면 “a가 b에게 준 수”를 2차원 리스트 give[0][1]에 적을 수 있다.
선물 지수는 “이 사람 줄의 합 − 이 사람 칸의 합”이다. 기록을 훑을 때 함께 세어 둔다.
짝마다 한 번만 보도록 i < j인 짝만 돈다. 그리고 규칙대로 둘 중 한 명의 “다음 달에 받을 수”를 1 늘린다.

떠올리는 신호: “모든 두 사람 사이” → 2차원 표. “이름으로 찾기” → 딕셔너리.

4단계 · 코드 흐름

idx = {이름: 번호}를 만든다.
n × n 표 give와 길이 n의 gave, got을 0으로 만든다.
기록마다 준 사람 i, 받은 사람 j를 번호로 바꿔 give[i][j], gave[i], got[j]를 1씩 늘린다.
짝 (i, j), i < j마다:
- give[i][j] > give[j][i]면 i가 받는다.
- give[i][j] < give[j][i]면 j가 받는다.
- 같으면 선물 지수를 비교해 큰 쪽이 받는다. 지수도 같으면 아무도 받지 않는다.
받는 수의 최댓값을 돌려준다.

5단계 · 파이썬 코드

def solution(friends, gifts):
    n = len(friends)
    idx = {name: i for i, name in enumerate(friends)}   # 이름 → 번호
    give = [[0] * n for _ in range(n)]                  # give[i][j]: i가 j에게 준 수
    gave, got = [0] * n, [0] * n
    for g in gifts:
        a, b = g.split()
        i, j = idx[a], idx[b]
        give[i][j] += 1
        gave[i] += 1
        got[j] += 1

    point = [gave[i] - got[i] for i in range(n)]        # 선물 지수
    receive = [0] * n                                   # 다음 달에 받을 수
    for i in range(n):
        for j in range(i + 1, n):                       # 짝마다 한 번씩
            if give[i][j] > give[j][i]:
                receive[i] += 1
            elif give[i][j] < give[j][i]:
                receive[j] += 1
            elif point[i] > point[j]:
                receive[i] += 1
            elif point[i] < point[j]:
                receive[j] += 1
    return max(receive)

[[0] * n for _ in range(n)]: 줄마다 따로 만든 n × n 표다. [[0] * n] * n으로 만들면 모든 줄이 같은 줄이 되어 틀린다.
range(i + 1, n): j를 i보다 큰 번호부터 돌려 같은 짝을 두 번 보지 않는다.
if … elif …: 위에서부터 처음 맞는 한 칸만 실행한다. 네 조건이 모두 틀리면(주고받은 수도, 지수도 같으면) 아무 일도 없다.

6단계 · 실행 추적

1단계의 예, 번호는 a = 0, b = 1, c = 2. point = [0, −1, 1]

짝 (i, j)	give[i][j] vs give[j][i]	지수 비교	받는 사람	receive
(0, 1)	2 > 1	볼 필요 없음	a	[1, 0, 0]
(0, 2)	0 < 1	볼 필요 없음	c	[1, 0, 1]
(1, 2)	0 = 0	−1 < 1	c	[1, 0, 2]

max(receive) = 2

7단계 · 복잡도와 흔한 실수

기록 G개를 한 번 훑고 짝 n²/2개를 보니 \(O(G + n^2)\)이다.

짝을 (i, j)와 (j, i)로 두 번 보면 선물이 두 배로 세어진다. 두 번 보려면 “i가 받는 경우”만 세야 한다.
선물 지수는 “준 수 − 받은 수”다. 순서를 바꾸면 반대 사람이 받는다.

검증: 문제의 예시 3개를 통과했고, 무작위 입력 1,000개에서 모든 순서쌍 (i, j)를 돌며 “i가 받는가”만 세는 다른 풀이와 결과가 같았다 — 04_pg258712_p1.py

프로그래머스 스쿨, “가장 많이 받은 선물” (https://school.programmers.co.kr/learn/courses/30/lessons/258712), 2026-09-30 조회. ↩