[프로그래머스 / python / Level 1] 가장 많이 받은 선물

문제

 

구현 문제이고, 2024 KAKAO WINTER INTERSHIP 1번으로 출제된 문제다.

레벨 1이라 정말 가벼운 마음으로 도전했는데 역시 구현이라 그런지 신경쓸 게 꽤 많아서 어디부터 어떻게 구현해야 할지 갈피를 잡는게 어려웠지만, 풀고 나면 언제나 그랬듯 딱히 어렵지 않게 느껴진다.

 

def solution(friends, gifts):
    
    # 더 많은 선물을 준 사람이, 다음 달에 선물을 하나 받는다
    # 주고받은 수가 같다면, 선물 지수가 큰 사람이 하나 받는다
    #   선물 지수: 자신이 친구들에게 준 선물 수 - 받은 선물 수 -> 즉 내가 더 많이 준 선물 수
    # 주고받은 수와 선물 지수 모두 같다면 -> 다음 달에 선물 주고받지 않는다
    
    # 가장 많이 받은 사람의 선물 수 출력하기
    
    # friends: ['john', 'sunkue' ...]
    # gifts: ['john sunkue', 'sunkue john' ...]
    
    n = len(friends)
    
    # 이름 : 인덱스 딕셔너리
    name_to_idx = dict()
    for i, name in enumerate(friends):
        name_to_idx[name] = i
    
    # 선물지수 계산을 위한 총 주고/받은 횟수
    total_give = [0] * n
    total_receive = [0] * n
    
    # 준 횟수 저장을 위한 2차원 배열 (give[i][j] -> i가 j에게 준 횟수)
    give = [[0] * n for _ in range(n)]
    for gift in gifts:
        
        # 인덱스 추출
        giver, receiver = gift.split()
        g_idx = name_to_idx[giver]
        r_idx = name_to_idx[receiver]
        
        # 준 횟수 갱신
        give[g_idx][r_idx] += 1
        total_give[g_idx] += 1
        total_receive[r_idx] += 1
    
    
    # 선물지수 계산
    present_score = [0] * n
    for i in range(n):
        present_score[i] = total_give[i] - total_receive[i]
    
    
    # 메인 로직
    next_month = [0] * n
    
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            
            i_to_j = give[i][j]
            j_to_i = give[j][i]
            
            if i_to_j > j_to_i:
                next_month[i] += 1
                
            elif i_to_j == j_to_i:
                if present_score[i] > present_score[j]:
                    next_month[i] += 1
    
    return max(next_month)

 

배열이 참 많이 필요하다.

 

1. 우선, 구현을 위해 여러 절차를 거치기 때문에 친구 이름을 인덱스로 매핑해 둔다. 딕셔너리가 사용되며, 아래 만들어지는 모든 배열의 인덱스는 친구 이름과 매핑된다.

2. 그리고 "준 횟수"를 저장하기 위한 2차원 배열 give를 만들고 할당한다. give[i][j] 는 i가 j에게 선물을 준 횟수이다.

3. 이번엔 "선물 지수"를 계산하기 위한 1차원 배열 total_give와 total_receive를 만들고(각 사람 당 주고 받은 총 횟수), gifts 리스트를 순회하며 값을 채워준다.

4. "선물 지수" 리스트를 만들고, 준 횟수 - 받은 횟수로 각 사람당 선물 지수를 계산해서 할당한다.

이제 준비가 완료되었다.

 

문제의 조건은 3개다.

1. 선물을 더 많이 준 사람이 받기

2. 똑같이 줬다면, 선물 지수가 높은 사람이 받기

3. 선물 지수도 같으면 주지 않는다

 

이제 2중 for문을 돌며 3가지 조건문을 계속해서 검사하며 결과 리스트 next_month에 값을 넣어준다.

마지막으로 가장 많이 받은 선물 개수인 max(next_month)를 리턴하면 된다.