99클럽 코테 스터디 TIL : 프로그래머스 258712 가장 많이 받은 선물

🚀 문제

https://school.programmers.co.kr/learn/courses/30/lessons/72412

🚀 정답 코드

def solution(friends, gifts):
    F = len(friends)  # 친구 수

    # 선물 주고받은 기록을 저장할 2차 딕셔너리 (gift_grid[A][B] = A가 B에게 준 선물 수)
    gift_grid = {}
    
    # 각 친구의 선물 지수 (준 선물 수 - 받은 선물 수)
    gift_values = {}
    
    # 다음 달에 선물을 받을 수 있는 친구 수를 저장할 리스트
    next_gift_grid = [0 for _ in range(F)]

    # 초기화: 모든 친구 쌍에 대해 선물 수를 0으로 설정
    for f1 in friends:
        gift_grid[f1] = {}
        gift_values[f1] = 0
        for f2 in friends:
            gift_grid[f1][f2] = 0

    # 선물 기록 반영: A가 B에게 선물을 준 경우, gift_grid[A][B] += 1
    for g in gifts:
        f, t = g.split()
        gift_grid[f][t] += 1

    # 각 친구의 선물 지수 계산 (준 선물 수 - 받은 선물 수)
    for f1 in friends:
        cur_gift_value = sum(gift_grid[f1].values())  # f1이 다른 친구들에게 준 총 선물 수
        for f2 in friends:
            if f1 == f2:
                continue
            cur_gift_value -= gift_grid[f2][f1]  # f1이 받은 선물 수만큼 차감
        gift_values[f1] = cur_gift_value

    # 다음 달에 선물을 받을 친구 계산
    for f1, idx in zip(friends, range(F)):
        for f2 in friends:
            if f1 == f2:
                continue
            # f1이 f2보다 선물을 더 많이 줬거나, 선물 수가 같지만 선물 지수가 높으면
            if (gift_grid[f1][f2] > gift_grid[f2][f1]) or \
               (gift_grid[f1][f2] == gift_grid[f2][f1] and gift_values[f1] > gift_values[f2]):
                next_gift_grid[idx] += 1  # f1이 다음 달에 받을 선물 개수 +1

    # 가장 많이 선물을 받을 친구의 개수 반환
    return max(next_gift_grid)

🚀 시행착오 했던 부분

구현 문제라 어려움은 없었지만 조금 개선할 수 있겠다고 생각한 부분이 있었다. 답안에서 선물 정보를 저장하는 자료구조로 dict를 활용했는데 dict를 활용하는 것보다 배열의 index를 통해서도 구현이 가능하고, 그 방향이 좀 더 속도가 빠르지 않을까 하는 생각에 아래와 같이 전체적으로 수정을 했었다.

def solution(friends, gifts):
    F = len(friends)  # 친구 수

    # 친구 이름을 인덱스로 매핑 (문자열 비교 대신 숫자 비교로 성능 최적화)
    name_to_idx = {name: idx for idx, name in enumerate(friends)}

    # 친구 간 선물 교환 횟수를 저장하는 2차원 배열
    # gift_grid[A][B] = A가 B에게 준 선물 횟수
    gift_grid = [[0] * F for _ in range(F)]

    # 각 친구의 선물 지수 (준 선물 수 - 받은 선물 수)
    gift_values = [0] * F

    # 다음 달에 받을 선물의 개수를 저장하는 배열
    next_gift_count = [0] * F

    # 선물 내역 반영
    for g in gifts:
        f, t = g.split()  # f가 t에게 선물을 줌
        f_idx = name_to_idx[f]
        t_idx = name_to_idx[t]
        gift_grid[f_idx][t_idx] += 1

    # 선물 지수 계산: 준 선물 수 - 받은 선물 수
    for i in range(F):
        give = sum(gift_grid[i])                     # i가 준 총 선물 수
        receive = sum(gift_grid[j][i] for j in range(F))  # i가 받은 총 선물 수
        gift_values[i] = give - receive

    # 다음 달에 선물을 받을지 여부 판단
    for i in range(F):
        for j in range(F):
            if i == j:
                continue  # 자기 자신과는 비교하지 않음

            # 조건 1: i가 j에게 준 선물이 더 많을 경우
            # 조건 2: 주고받은 횟수 같지만 i의 선물 지수가 더 높을 경우
            if (gift_grid[i][j] > gift_grid[j][i]) or \
               (gift_grid[i][j] == gift_grid[j][i] and gift_values[i] > gift_values[j]):
                next_gift_count[i] += 1

    # 가장 많은 선물을 받게 될 친구가 받을 선물 개수 반환
    return max(next_gift_count)

결과적으로는 어느 정도 성과가 있긴 했다. 빨간색이 개선전, 주황색이 개선후 제출 결과이다.

인원 마다 몇 개의 선물을 주고 받았는지 다 알아야한다는 점에서 dict가 바로 떠오르긴 했지만 이런 과정을 통해서 배열에 좀 더 익숙해지는 연습을 해봐야겠다.