2024 KAKAO WINTER INTERNSHIP 가장 많이 받은 선물

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

프로그래머스

자료 구조까지 예시로 제공되어 풀기 쉽도록 만든 문제..

매번 friends에서 원소의 위치를 찾는 것은 비효율적이다.
딕셔너리(맵, 해시)를 이용해 O(1)로 위치를 찾도록 하자.  

def solution(friends, gifts):
    friend_index = {friend: index for index, friend in enumerate(friends)}
    gift_table = [[0 for _ in friends] for _ in friends]
    gift_factor = [0 for _ in friends]
    results = [0 for _ in friends]
    for _from, _to in map(lambda x: x.split(' '), gifts):
        gift_table[friend_index[_from]][friend_index[_to]] += 1
        gift_factor[friend_index[_from]] += 1
        gift_factor[friend_index[_to]] -= 1
    for i in range(len(friends)):
        for j in range(len(friends)):
            if gift_table[i][j] > gift_table[j][i]:
                results[i] += 1
            elif gift_table[i][j] == gift_table[j][i] and gift_factor[i] > gift_factor[j]:
                results[i] += 1
    return max(results)

map 대신 제너레이터 익스프레션을 사용해도 됨. 

def solution(friends, gifts):
    friend_index = {friend: index for index, friend in enumerate(friends)}
    gift_table = [[0 for _ in friends] for _ in friends]
    gift_factor = [0 for _ in friends]
    results = [0 for _ in friends]
    for _from, _to in (x.split(' ') for x in gifts):
        gift_table[friend_index[_from]][friend_index[_to]] += 1
        gift_factor[friend_index[_from]] += 1
        gift_factor[friend_index[_to]] -= 1
    for i in range(len(friends)):
        for j in range(len(friends)):
            if gift_table[i][j] > gift_table[j][i]:
                results[i] += 1
            elif gift_table[i][j] == gift_table[j][i] and gift_factor[i] > gift_factor[j]:
                results[i] += 1
    return max(results)