작심 큰일 챌린지 - 가장 많이 받은 선물 (파이썬)

새로 배운 개념이나 기술:
시간 복잡도를 낮추기 위해 문자열 대신 인덱스를 사용하는 방법을 다시 한 번 배웠다. 또한 친구a-친구b 처럼 쌍으로 관계가 있는 경우는 2차원 배열로 정의하면 추후 관계에 따른 조건 처리가 쉬워진다.
필요한 정보를 반복문 안에서 매번 계산하는 것보단 미리 다 구해놓고 배열로 저장한 후 필요할 때만 뽑아서 쓰는 것이 시간을 더 줄일 수 있는 방법이다.

어려웠던 점과 해결 방법:
조건을 제대로 파악한 후 구현에 옮기는 것이 어려웠다. 예를 들어 처음에는 친구a = [준 횟수, 받은 횟수, 선물 지수] 형태의 딕셔너리로 필요한 정보들을 저장하려고 했지만 이렇게 해버리면 a가 누구와 선물을 주고 받았는지의 정보가 나오지 않아 이 방법은 좋은 방법이 아니었다. 
친구들끼리의 정보를 표시하기 위해 2차원 배열로 정의했더니 누가 누구에게 몇 번 선물을 줬는지 한 눈에 알아볼 수 있었고 이를 통해 선물 지수도 한 번에 저장할 수 있었다.
마지막으로 모든 친구들은 쌍으로 정보가 들어오므로 for문을 돌릴 때 중복 되는 정보가 없도록 주의해줬다.

 

def solution(friends, gifts):
    # 규칙1: a<->b 주고받은 기록이 있다면 더 많이 준 사람의 선물 +1
    # 규칙2: a<->b 주고받은 기록이 없다면 선물 지수 큰 사람의 선물 +1
    # 규칙3: a<->b 주고받은 기록 없고, 선물 지수도 같다면 +0 (pass)
    
    # 계산하기 편하게 이름을 인덱스로 변환
    friends_name = {name: idx for idx, name in enumerate(friends)}
    n = len(friends)
    # gift_matrix[i][j]: i가 j에게 준 선물 수
    gift_matrix = [[0]*n for _ in range(n)]
    
    # gifs 사용할 수 있는 정보로 바꾸기
    # 선물 지수
    gift_indices = [0]*n
    for gift in gifts:
        giver, receiver = gift.split()
        gift_matrix[friends_name[giver]][friends_name[receiver]] += 1
        gift_indices[friends_name[giver]] += 1
        gift_indices[friends_name[receiver]] -= 1
    # 각 사람이 받게 될 선물 수
    next_gift = [0]*n
    for i in range(n):
        for j in range(i+1, n): # 두 친구로 만들 수 있는 모든 '쌍(pair)'을 중복 없이 딱 한 번씩만 확인하기 위함
        # if j in range(n)이면 쌍이 중복되므로 결과 //2를 해줘야 한다.
            if gift_matrix[i][j] < gift_matrix[j][i]:
                next_gift[j] += 1
            elif gift_matrix[i][j] > gift_matrix[j][i]:
                next_gift[i] += 1
            else: # gift_matrix[i][j] == gift_matrix[j][i]:
                if gift_indices[i] > gift_indices[j]:
                    next_gift[i] += 1
                elif gift_indices[i] < gift_indices[j]:
                    next_gift[j] += 1
                  
    answer = max(next_gift)
            
    return answer