[프로그래머스] 가장 많이 받은 선물(파이썬, 구현, 2024 KAKAO WINTER INTERNSHIP)

 

 

🌱 문제

프로그래머스

 

🌱 풀이

1. 변수 설정

문제 설명에 위와 같이 주고받은 선물과 선물 지수를 표로 나타내주는데, 이걸 그래도 구현하면 됩니다!

table은 주고받은 선물의 개수를 담을 2차원 리스트이고, gift_index는 선물지수를 저장할 리스트입니다. answer는 다음 달에 각각 받을 선물 개수를 담을 리스트이다. 즉, answer 리스트에 있는 최댓값이 정답이 됩니다.

table = [[0 for _ in range(len(friends))] for __ in range(len(friends))]
gift_index = [0] * len(friends)
answer = [0] * len(friends)

 

2. 주고받은 선물 개수와 선물 지수 세기

주고 받은 선물 기록을 담은 1차원 문자열 배열 gifts 리스트를 반복문으로 돌면서 선물지수와 주고받은 선물 개수를 카운팅해서 table과 gift_index를 채워나갑니다.

for gift in gifts:
    give, take = gift.split(" ")
    give_idx, take_idx = friends.index(give), friends.index(take)
    gift_index[give_idx] += 1
    gift_index[take_idx] -= 1
    table[give_idx][take_idx] += 1

 

3. 다음달에 받을 선물 계산하기

 

2차원 리스트 table을 제대로 채우면 위와 같이 완성되었을 것입니다. 이제 이 table을 돌면서 받을 선물의 개수를 계산해주면되는데, 위의 그림에서 같은 색의 칸끼리 대소비교를 해서 더 선물을 많이 준 사람이 다음 달에 받을 선물을 +1 해줍니다. 대소비교를 했는데 값이 같다면 선물 지수를 비교하면됩니다.

따라서 2차원 리스트를 모두 반복문으로 돌 필요가 없고, 반만 돌면 됩니다! 따라서 시간 복잡도는 $O(\frac{n^2}{2})$가 됩니다.

 

for i in range(len(friends)):
    for j in range(i + 1, len(friends)):
        if table[i][j] > table[j][i]:  # i가 준 횟수가 더 많음
            answer[i] += 1
        elif table[i][j] < table[j][i]:  # j가 준 횟수가 더 많음
            answer[j] += 1
        else:
            if gift_index[i] > gift_index[j]:
                answer[i] += 1
            elif gift_index[i] < gift_index[j]:
                answer[j] += 1

 

🌱 정답

def solution(friends, gifts):
    answer = [0] * len(friends)
    table = [[0 for _ in range(len(friends))] for __ in range(len(friends))]
    
    # 선물 지수 계산
    gift_index = [0] * len(friends)
    for gift in gifts:
        give, take = gift.split(" ")
        give_idx, take_idx = friends.index(give), friends.index(take)
        gift_index[give_idx] += 1
        gift_index[take_idx] -= 1
        table[give_idx][take_idx] += 1
                        
    for i in range(len(friends)):
        for j in range(i + 1, len(friends)):
            if table[i][j] > table[j][i]: # i가 준 횟수가 더 많음
                answer[i] += 1
            elif table[i][j] < table[j][i]: # j가 준 횟수가 더 많음
                answer[j] += 1
            else:
                if gift_index[i] > gift_index[j]:
                    answer[i] += 1
                elif gift_index[i] < gift_index[j]:
                    answer[j] += 1

    return max(answer)